我努力奔跑,只为追上曾经被寄予厚望的自己

CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

2018-11-02 16:21:33


题意:一棵以 $1$ 为根的树上,每条边都有一个 $a$ 到 $v$ 之间的字母

   一条路径被称为“好路径”当且仅当其上字母可以经过重新排序后成为一个回文串。

   对于每个子树,求出其中最长的“好路径”的长度。


把字母转化为边权 $dis=2^{ch-'a'}$

一条路径称为“好路径”的条件就是:这条路径的边权异或和在二进制下最多有一个 $1$

对于每个子树都要计算答案, $dp$ 和数据结构好像都难以完成

好像还有一个奇妙的东西?树上 $dsu$ !

类似淀粉质,开一个桶, $f[i]$ 表示从根开始异或和为 $i$ 的最大深度

预处理出每个子树的 $dfs$ 序

先递归处理轻儿子,删除轻儿子的贡献,递归处理重儿子,把轻儿子再算一遍

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=5e5+5;
struct node
{
    int to,nxt,dis;
}edge[N<<1];
int n,num,head[N],dep[N],dis[N],tot[N],idx[N],a[N];
int tim,L[N],R[N],son[N],ans[N],f[1<<22];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num]=(node){to,head[from],dis}; 
    head[from]=num;
}
void dfs(int k,int fa)
{
    a[idx[k]=L[k]=++tim]=k; tot[k]=1; dep[k]=dep[fa]+1;
    for (reg int i=head[k],bigson=0;i;i=edge[i].nxt)
    {
        int v=edge[i].to,d=edge[i].dis; 
        dis[v]=dis[k]^d; dfs(v,k); tot[k]+=tot[v];
        if (bigson<tot[v]) bigson=tot[v],son[k]=v;
    }
    R[k]=tim;
}
void DFS(int k,bool flag)
{
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v!=son[k]) DFS(v,0),ans[k]=max(ans[k],ans[v]);
    }
    if (son[k]) DFS(son[k],1),ans[k]=max(ans[k],ans[son[k]]);
    if (f[dis[k]]) ans[k]=max(ans[k],f[dis[k]]-dep[k]);
    for (reg int i=0;i<22;i++)
      if (f[dis[k]^(1<<i)]) ans[k]=max(ans[k],f[dis[k]^(1<<i)]-dep[k]);
    f[dis[k]]=max(f[dis[k]],dep[k]);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==son[k]) continue;
        for (reg int j=L[v];j<=R[v];j++)
        {
            if (f[dis[a[j]]]) ans[k]=max(ans[k],f[dis[a[j]]]+dep[a[j]]-(dep[k]<<1));
            for (reg int c=0;c<22;c++)
              if (f[dis[a[j]]^(1<<c)]) ans[k]=max(ans[k],f[dis[a[j]]^(1<<c)]+dep[a[j]]-(dep[k]<<1));
        }
        for (reg int j=L[v];j<=R[v];j++) f[dis[a[j]]]=max(f[dis[a[j]]],dep[a[j]]);
    }
    if (!flag) for (reg int i=L[k];i<=R[k];i++) f[dis[a[i]]]=0;
}
int main()
{
    n=read();
    for (reg int i=2;i<=n;i++)
    {
        int x=read();
        char c=getchar();
        while (c<'a'||c>'v') c=getchar();
        add_edge(x,i,(1<<(c-'a')));
    }
    dfs(1,0); DFS(1,0);
    for (reg int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}