这题思路就还行!

1.思路

可以思考下如何判断回文串,回文串的组成必定奇数字母小于等于一个.如此,我们把每个数都表示成二进制的形式.只和奇偶有关.这里开(1<<23)即可.D[u]表示从根节点1到u节点,a-v的奇偶性情况.然后我们只需要开个C数组,C[D[u]]表示当前子树下,值为D[u]的节点最深的深度是多少,考虑合法的方案数,必然答案是2^i/0才能组成回文串对吧?然后又贪心+dp一下.首先子树的最长回文串可能就是子树中的答案,然后还可能是根节点到某个子树的分支,最后可能是根节点到两个子树的分支,取个max大功就告成了!

2.代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50,M=(1<<23)+5;
int D[N],C[M];
vector<int>v[N];
int P,dfn[N],sz[N],dep[N],ans[N];
void init(int u,int fa)
{
    C[D[u]]=-2e9;
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        init(son,u);
    }
}

void up_ans(int u,int fa)//更新答案.
{
    ans[P]=max(ans[P],dep[u]+C[D[u]]);
    for(int i=0;i<22;i++)
    {
        ans[P]=max(ans[P],dep[u]+C[D[u]^(1<<i)]);
    }
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        up_ans(son,u);
    }
}

void up_C(int u,int fa)//更新C数组
{
    C[D[u]]=max(C[D[u]],dep[u]);
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        up_C(son,u);
    }
}

void dfs(int u,int fa)
{
    sz[u]=1;dep[u]+=dep[fa]+1;D[u]^=D[fa];
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa) continue;
        dfs(son,u);
        sz[u]+=sz[son];
        if(sz[dfn[u]]<sz[son])  dfn[u]=son;
    }
}

void Dfs(int u,int fa)
{
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa||son==dfn[u])    continue;
        Dfs(son,u),init(son,u);
    }
    if(dfn[u])    Dfs(dfn[u],u);
    //统计答案.
    P=u;
    for(int i=0;i<(int)v[u].size();i++)//再遍历一次子树统计答案.
    {
        int son=v[u][i];
        if(son==fa||son==dfn[u])   continue;
        up_ans(son,u);
        up_C(son,u);
    }//这只是横跨两边的答案.
    C[D[u]]=max(C[D[u]],dep[u]);
    ans[u]=max(ans[u],dep[u]+C[D[u]]);
    for(int i=0;i<22;i++)
    {
        ans[u]=max(ans[u],dep[u]+C[(1<<i)^D[u]]);
    }ans[u]-=(dep[u]<<1);//横跨一边的答案.
    for(int i=0;i<(int)v[u].size();i++)
    {
        int son=v[u][i];
        if(son==fa)    continue;
        ans[u]=max(ans[u],ans[son]);
    }
}

int main()
{
    memset(C,-0x3f,sizeof C);
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        int x;scanf("%d",&x);
        v[i].push_back(x);
        v[x].push_back(i);
        char s[2];scanf("%s",s);
        if(s[0]>'v'||s[0]<'a')   continue;
        D[i]=(1<<(s[0]-'a'));
    }
    dfs(1,0);
    Dfs(1,0);
    //puts("1");
    for(int i=1;i<=n;i++)   printf("%d ",ans[i]);
    puts("");
    return 0;
}