题解 CF741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】
Farkas_W
·
·
题解
\text{CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths}
$\quad$这其实算一道 Dsu 的压轴题，据说是树上启发式合并算法的创始者出的题。
$\quad$这题确实是有些难度的，总之我一开始连题解都没有看懂。
$\quad$首先考虑回文的问题，其他题解其实讲的很清楚了，只要22个字母中最多有一个字母数量为奇数即可，也可都为偶数，所以一共23种情况，但考虑所有情况(只分奇偶)有 $2^{22}$中情况，可以用一个二进制数表示，**用 $cnt_i$ 表示二进制数为 $i$ 的结点的最大深度，二进制数指的是从这个结点到根节点的最短路径的序列，$num_x$ 表示结点 $x$ 到根节点的最短路径的序列**，请仔细理解这句话，否则之后的代码可能会看不懂。
$\quad$然后我们对于两个修改函数都讲一遍。
$\quad$第一个修改函数，就是判断是否有有符合条件的，如对于节点 $x$ 来说，和TA到根节点的序列为 $num_x$，$cnt_{num_x}$ 表示之前出现的另一条大小为 $num_x$ 序列，这样这两条路径合并后字母数就都是偶数，之后的循环枚举的是有一个字母不同的情况，这两种情况都是符合条件的。
```cpp
il void add1(int x)
{
ans[now]=max(ans[now],dep[x]+cnt[num[x]]);
for(re i=0;i<=21;i++)ans[now]=max(ans[now],dep[x]+cnt[(1<<i)^num[x]]);
}
```
$\quad$对于第二个修改函数，就是把这个结点 $x$ 的信息载入 $cnt$ 数组，并且为了最后的序列最长，要尽可能选深度大的，显然深度大的答案更优。
```cpp
il void add2(int x)
{cnt[num[x]]=max(cnt[num[x]],dep[x]);}
```
$\quad$注意要先做修改操作 $1$，再做修改操作 $2$，也就是说先统计这个点的答案(或一棵子树)，再载入这个点的数据(或一棵子树)，否则答案会把自己也记进去，可以仔细思考一下这个点。
$\quad$接下来我们思考一个问题，因为我们是一棵子树一棵子树为单位修改的，如果这个最优答案在子树中会怎么样？可以发现这样的答案在子树中一定被统计过了，当这条路径的两个端点的LCA被询问时就以及被记录了，所以还要跑一遍所有子树，用子树的答案来更新当前结点。
$\quad$另外我们还要注意节点 $i$ 的答案的计算公式为
$$ans_i=\max (dep_x+dep_y-2\times dep_i)$$
$\quad$这其实就是 $x$，$y$ 两点之间的距离公式( $x$,$y$ 为最短路径的两个端点)，另外可以发现最优情况下结点 $i$ 为结点 $x$ 和结点 $y$ 的LCA，因为结点 $x$ 和结点 $y$ 的在以 $i$ 为根节点的子树，若不是的话，那么答案就会算多，但这显然是错误的答案，所以我们是一棵子树一棵子树为单位修改的，这也算回答了上面的问题。
$\quad$最后来看看完整代码吧！
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
#define re register int
#define il inline
#define next nee
#define inf 1e9+5
il int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
il void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)print(x/10);
putchar(x%10+'0');
}
const int N=5e5+5;
int n,m,next[N],go[N],head[N],tot,seg[N],son[N],father[N],now;
int size[N],rev[N],ans[N],s[N],dep[N],num[N],cnt[1<<23];
il int Max(int x,int y){return x>y?x:y;}
il void Add(int x,int y,int z)
{
next[++tot]=head[x];
head[x]=tot;go[tot]=y;s[tot]=z;
}
il void add1(int x)//修改操作1
{
ans[now]=max(ans[now],dep[x]+cnt[num[x]]);
for(re i=0;i<=21;i++)ans[now]=max(ans[now],dep[x]+cnt[(1<<i)^num[x]]);
}
il void add2(int x)//修改操作2
{cnt[num[x]]=max(cnt[num[x]],dep[x]);}
il void clear(int x)//清空操作
{
for(re i=seg[x];i<=seg[x]+size[x]-1;i++)
cnt[num[rev[i]]]=-inf;
}
il void dfs1(int x)
{
dep[x]=dep[father[x]]+1;size[x]=1;seg[x]=++seg[0];rev[seg[x]]=x;
for(re i=head[x],y;i,y=go[i];i=next[i])
{
num[y]=num[x]^(1<<s[i]);dfs1(y);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
il void dfs2(int x,int flag)
{
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(y==son[x])continue;
dfs2(y,0);
}if(son[x])dfs2(son[x],1);now=x;
for(re i=head[x],y;i,y=go[i];i=next[i])
{
if(y==son[x])continue;
for(re i=seg[y];i<=seg[y]+size[y]-1;i++)add1(rev[i]);
for(re i=seg[y];i<=seg[y]+size[y]-1;i++)add2(rev[i]);
}add1(x),add2(x);//记得要修改x结点
ans[x]-=(dep[x]<<1);//减去本身的深度
for(re i=head[x],y;i,y=go[i];i=next[i])ans[x]=max(ans[x],ans[y]);
if(!flag)clear(x);
}
signed main()
{
n=read();char ch;
for(re i=0;i<(1<<22);i++)cnt[i]=-inf;//一定要初始化为负值
for(re i=2,x;i<=n;i++){x=read();father[i]=x;scanf("%c",&ch);Add(x,i,ch-'a');}
dfs1(1);dfs2(1,1);
for(re i=1;i<=n;i++)print(Max(ans[i],0)),putchar(' ');//可能会输出负数
return 0;
}
```