CF741D Mehrdad’s Dokhtar-kosh paths

思路：

1.与前面的题不同的是，这是一类无修改统计链信息的问题
2.一个串能重排形成是回文串当且仅当其字符数量均为偶数或者恰好有一个奇数，实际上对于任意的一条路径我们只关注其任意字符的奇偶性
3.因为只有 $22$ 个字符，所以可以用二进制状压到 $0 \sim 2^{22}-1$
4， $Xor[i]$ 表示节点 $i$ 到根结点的异或值
5.假设现在我们处理以 $u$ 为根的子树，如果一条链从 $u$ 开始，一直连到他的某一个子树中的点，贪心地，这个点的深度一定是所有满足条件的点中最深的
5. $maxx$ 维护最长的 $Dokhtar-kosh$ 路径的长度
6.以 $u$ 为根的子树中，考虑怎么更新 $maxx$ ：
(1)从儿子的子树中来, $maxx=max(maxx,ans[son]),son$ 是 $u$ 所有的儿子
(2) $u$ 和子树中的某个点连接起来
(3)考虑跨子树组合成一条链
7，两个点 $a、b$ 的简单路符合要求一定满足下列条件之一：
(1) $Xor[a]⊕Xor[b]==0$
(2) $Xor[a]⊕Xor[b]==2^i$
8.由于我们的贪心性质，我们维护一个数组 $cnt[i]$ ，表示异或值 $i$ 最深的深度
9. $a、b$ 的简单路的长度 $=dep[a]+dep[b]-2*dep[lca(a,b)]$
10.由于这题的特殊性，不能在维护 $maxx$ 的同时维护 $cnt[i]$ ，而且在做以 $u$ 为根结点的子树的答案时i，需要调用 $calc(v)$ ，对以 $u$ 的子树信息进行统计，所以不需要 $vis[i]$ 标记重儿子来绕过重儿子。
11.每次调用 $calc(v)$ 后调用 $update(v)$ 更新数组 $cnt[i]$ 。

MyCode:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7,maxm=5e5+7;
typedef long long ll;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
char val[maxm];
int head[maxn],Next[maxm],to[maxm],tot;
void add(int x,int y,char ch) {
    to[++tot]=y;
    Next[tot]=head[x];
    val[tot]=ch;
    head[x]=tot;
}
int size[maxn],son[maxn];
int ans[maxn],cnt[1<<22],dep[maxn],Xor[1<<22],maxx;
void dfs1(int x,int f) {
    size[x]=1;
    dep[x]=dep[f]+1;
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(v==f) continue;
        Xor[v]=Xor[x]^(1<<(val[i]-'a'));
        dfs1(v,x);
        size[x]+=size[v];
        if(size[son[x]]<size[v]) son[x]=v;
    }
}
int Now;
void calc(int x) {
    if(cnt[Xor[x]]) maxx=max(maxx,dep[x]+cnt[Xor[x]]-Now);
    for(int i=0;i<=21;++i) if(cnt[(1<<i)^Xor[x]])
        maxx=max(maxx,dep[x]+cnt[(1<<i)^Xor[x]]-Now);
    for(int i=head[x];i;i=Next[i])
        calc(to[i]);
}
void delet(int x) {
    cnt[Xor[x]]=0;
    for(int i=head[x];i;i=Next[i])
        delet(to[i]);
}
void update(int x) {
    cnt[Xor[x]]=max(cnt[Xor[x]],dep[x]);
    for(int i=head[x];i;i=Next[i])
        update(to[i]);
}
void dfs2(int x,bool opt) {
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(son[x]==v) continue;
        dfs2(v,false);
    }
    if(son[x]) dfs2(son[x],true);
    Now=dep[x]<<1;
    for(int i=head[x];i;i=Next[i]) maxx=max(maxx,ans[to[i]]);
    for(int i=head[x],v;i;i=Next[i]) {
        v=to[i];
        if(son[x]==v) continue;
        calc(v);
        update(v);
    }
    if(cnt[Xor[x]]) maxx=max(maxx,dep[x]+cnt[Xor[x]]-Now);
    for(int i=0;i<=21;++i) if(cnt[(1<<i)^Xor[x]])
        maxx=max(maxx,dep[x]+cnt[(1<<i)^Xor[x]]-Now);
    if(!cnt[Xor[x]]) cnt[Xor[x]]=dep[x];
    ans[x]=maxx;
    if(!opt) {
        delet(x);
        maxx=0;
    }
}
int main() {
    int n;
    char ch;
    scanf("%d",&n);
    for(int i=2,u;i<=n;++i) {
        scanf("%d %c",&u,&ch);
        add(u,i,ch);
    }
    dfs1(1,0);
    dfs2(1,false);
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    return 0;
}