「CF741DArpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths」

题目

这题目名字怎么这么长

zky学长讲过的题

非常显然，就是重排之后能形成回文串的话，最多只能有一个字母出现奇数次

又发现这个字符集大小只有\(22\)，于是套路的使用状压，把每一条边转化成一个二进制数，求一下根路径前缀异或和

由于异或的性质，我们想得到路径\((x,y)\)的异或值，只需要\(pre_x \bigoplus pre_y\)就可以了

于是我们\(dsu\ on\ tree\)，统计一个子树里所有的\(pre\)之后枚举一下拼成什么就好了

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define LL long long
#define re register
#define maxn 500005
inline int read() {
int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int n,num,Son,ans;
struct E{int v,nxt,w;}e[maxn];
int head[maxn],pre[maxn],deep[maxn],mx[5000005],vis[5000005];
int sum[maxn],son[maxn],Ans[maxn];
inline void add(int x,int y,int z) {e[++num].v=y;e[num].w=z;e[num].nxt=head[x];head[x]=num;}
void dfs1(int x) {
sum[x]=1;int maxx=-1;
for(re int i=head[x];i;i=e[i].nxt) {
if(deep[e[i].v]) continue;
deep[e[i].v]=deep[x]+1;pre[e[i].v]=pre[x]^e[i].w;
dfs1(e[i].v);sum[x]+=sum[e[i].v];
if(sum[e[i].v]>maxx) maxx=sum[e[i].v],son[x]=e[i].v;
}
}
inline void ask(int x) {
if(vis[pre[x]]) ans=max(ans,deep[x]+mx[pre[x]]);
int now=pre[x];
for(re int i=0;i<22;i++)
if(vis[now^(1<<i)]) ans=max(ans,deep[x]+mx[now^(1<<i)]);
}
void calc(int x,int opt) {
if(opt==1) ask(x);
else mx[pre[x]]=0,vis[pre[x]]--;
for(re int i=head[x];i;i=e[i].nxt)
if(Son!=e[i].v) calc(e[i].v,opt);
}
void add(int x) {
mx[pre[x]]=max(mx[pre[x]],deep[x]);vis[pre[x]]++;
for(re int i=head[x];i;i=e[i].nxt) add(e[i].v);
}
void dfs(int x,int opt) {
for(re int i=head[x];i;i=e[i].nxt)
if(son[x]!=e[i].v) dfs(e[i].v,0);
if(son[x]) dfs(son[x],1);
Son=son[x],ans=0;ask(x);
mx[pre[x]]=max(mx[pre[x]],deep[x]);vis[pre[x]]++;
for(re int i=head[x];i;i=e[i].nxt)
if(son[x]!=e[i].v) calc(e[i].v,1),add(e[i].v);
Son=0;Ans[x]=ans-2*deep[x];
if(!son[x]) Ans[x]=0;
if(!opt) calc(x,0);
for(re int i=head[x];i;i=e[i].nxt) Ans[x]=max(Ans[x],Ans[e[i].v]);
}
int main() {
n=read();char ch;
for(re int fa,i=2;i<=n;i++)
fa=read(),ch=getchar(),add(fa,i,1<<(ch-'a'));
deep[1]=1,dfs1(1);dfs(1,1);
for(re int i=1;i<=n;i++) printf("%d ",Ans[i]);
return 0;
}