CF-741D 题解 - 洛谷保存站

[题目传送门 CF741D](https://codeforces.com/problemset/problem/741/D)

题目大意：一棵树的边上有一些字母。对于每颗子树，要找到该子树中一条链，这条链所经过的边上字母经过调整后可以形成回文串。

---

算法：树上启发式合并 $+$ 状压优化。

可以将 $a$ 表示成 $2^0$，

将 $b$ 表示成 $2^1$，

将 $c$ 表示成 $2^2$，

......

可知路径上的字母异或后为 $0$ 或 $2^i$，

才是合法的字符串，

用 $cal_i$ 表示当前在 $u$ 的子树中从根异或到 $v$ 节点的结果为 $i$ 的最大深度。

有 $3$ 种更新答案的方法：

1.子节点的答案

2.从当前 $u$ 节点到 $u$ 的子树中

3.子树中经过 $u$ 节点的路径

对于情况 $1$，由儿子节点更新答案，

对于情况 $2.\ 3$，枚举 $u$ 的子树的每个节点。

---

### Code

```cpp
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <bitset>
using namespace std;
const int M=(1<<22)+10,N=5e5+10;
int n,tot;
int fst[N],nxt[N],to[N],wei[N],fa[N],ex[N],dep[N];
int cnt[N],hson[N],ans[N],cal[M],ord[N],dis[N],ed[N];
char op;
void add_road(int ui,int vi,int wi)
{
	to[++tot]=vi,wei[tot]=wi,
	nxt[tot]=fst[ui],fst[ui]=tot;
}
void dfs(int x)
{
	cnt[x]=1,dep[x]=dep[fa[x]]+1;
	ord[x]=++tot;
	dis[tot]=x;
	for (int i=fst[x];i;i=nxt[i])
	{
		if (to[i]==fa[x]) continue;
		ex[to[i]]=ex[x]^wei[i];
		dfs(to[i]);
		if (cnt[hson[x]]<cnt[to[i]]) hson[x]=to[i];
		cnt[x]+=cnt[to[i]];
	}
	ed[x]=tot;
}
void calc(int x)
{
	for (int i=0;i<=(1<<21);i<<=1,i+=!i)
		if (cal[i^ex[x]])
			ans[x]=max(ans[x],cal[i^ex[x]]-dep[x]);
	cal[ex[x]]=max(cal[ex[x]],dep[x]);
	for (int i=fst[x];i;i=nxt[i])
	{
		int y=to[i];
		if (y==fa[x]||y==hson[x]) continue;
		for (int j=ord[y];j<=ed[y];j++)
		{
			int z=dis[j];
			for (int q=0;q<=(1<<21);q<<=1,q+=!q)
				if (cal[q^ex[z]])
					ans[x]=max(ans[x],cal[q^ex[z]]+dep[z]-2*dep[x]);
		}
		for (int j=ord[y];j<=ed[y];j++) cal[ex[dis[j]]]=max(cal[ex[dis[j]]],dep[dis[j]]);
	}
}
void dfs(int x,bool flag)
{
	for (int i=fst[x];i;i=nxt[i])
	{
		if (to[i]==fa[x]||to[i]==hson[x]) continue;
		dfs(to[i],1),ans[x]=max(ans[x],ans[to[i]]);
	}
	if (hson[x]) dfs(hson[x],0),ans[x]=max(ans[x],ans[hson[x]]);
	calc(x);
	if (flag)
		for (int i=ord[x];i<=ed[x];i++) cal[ex[dis[i]]]=0;
}
int main()
{
	cin>>n;
	for (int i=2;i<=n;i++)
	{
		scanf("%d %c",&fa[i],&op);
		add_road(fa[i],i,1<<(op-'a'));
	}
	tot=0,dfs(1);
	dfs(1,0);
	for (int i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}
```

正在渲染内容...