反正就是利用重链剖分：一个点到根最多只会经过 \(\log N\) 条轻边。然后就对于一个点，求其子树内的一些东西，要记录这个子树内所有节点的某些信息——这个点的重儿子递归下去不清空信息，轻儿子递归下去清空信息，然后对于这个节点又把轻儿子及它们的子树内节点记录一遍，再计算这个点的贡献。
比如例题 CF741D，当知道结论之后，记录下每个节点到根的字符集状压和，在某个点为根的子树内算答案就是在这个子树内找到 \(2\) 个点，满足这两个点异或起来的 popcount 小于等于 \(1\)，然后然后这 \(2\) 个点的距离最远——答案就是这个最远距离。
如何求这个答案：算完所有儿子的答案，这个点的答案至少为所有儿子的答案的 max——即不经过这个点的链。
对于经过这个点的链：这个点为链端或任意两个不相同子树内的点为链端点。
然后开一个桶记录当前有的字符集，每次把一个轻儿子的子树内所有节点能取得的最大贡献算出，再把这些点加进这个桶。在这些最大贡献里再取最大，当前答案就显然可得。
对于这个点到其父亲是重边：不删除刚才加入的轻儿子及其子树内的点。
反之：删除这个子树内的所有点——因为它兄弟还要算。（它父亲的重儿子最后算，所以不用删）
具体见代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+50,MAX=(1<<22)|50;
int N;
struct Edge
{
int x,y,Next;
}e[MAXN<<1];
int elast[MAXN],tot;
void Add(int x,int y)
{
tot++;
e[tot].x=x;
e[tot].y=y;
e[tot].Next=elast[x];
elast[x]=tot;
}
int Size[MAXN],Son[MAXN];
int ch[MAXN];
int Cnt[MAX];
int ans[MAXN];
int In[MAXN],Out[MAXN],Back[MAXN],CNT;
int depth[MAXN];
void dfs1(int u)
{
CNT++;
In[u]=CNT;
Back[CNT]=u;
Size[u]=1;
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
ch[v]^=ch[u];
depth[v]=depth[u]+1;
dfs1(v);
Size[u]+=Size[v];
if(Size[Son[u]]<Size[v])
{
Son[u]=v;
}
}
Out[u]=CNT;
}
int Query(int S,int x,int Lca)
{
int Max=0;
if(Cnt[S])
Max=max(Max,Cnt[S]+depth[x]-2*depth[Lca]);
for(int i=0;i<22;i++)
{
if(Cnt[S^(1<<i)])
{
Max=max(Max,Cnt[S^(1<<i)]+depth[x]-2*depth[Lca]);
}
}
return Max;
}
void dfs2(int u,int op)
{
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
if(v==Son[u])
continue;
dfs2(v,0);
ans[u]=max(ans[u],ans[v]);
}
if(Son[u])
{
dfs2(Son[u],1);
ans[u]=max(ans[u],ans[Son[u]]);
}
ans[u]=max(ans[u],Query(ch[u],u,u));
Cnt[ch[u]]=max(Cnt[ch[u]],depth[u]);
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
if(v==Son[u])
continue;
for(int j=In[v];j<=Out[v];j++)
{
ans[u]=max(ans[u],Query(ch[Back[j]],Back[j],u));
}
for(int j=In[v];j<=Out[v];j++)
{
Cnt[ch[Back[j]]]=max(Cnt[ch[Back[j]]],depth[Back[j]]);
}
}
if(op==0)
{
for(int i=In[u];i<=Out[u];i++)
{
Cnt[ch[Back[i]]]=0;
}
}
}
int fa;
char op[3];
int main()
{
scanf("%d",&N);
for(int i=2;i<=N;i++)
{
scanf("%d%s",&fa,&op[1]);
ch[i]=1<<(op[1]-'a');
Add(fa,i);
}
depth[1]=1;
dfs1(1);
dfs2(1,1);
for(int i=1;i<=N;i++)
{
printf("%d ",ans[i]);
}
}
每个点当到根的路径上遇到轻边才会被加入和删除一次，因为遇到的轻边不大于 \(\log N\) 条，所以每个点被加入和删除的次数也是不大于这么多次——所以时间复杂度很低。
DSU on Tree 可以处理计算一个子树内问题需要知道这个子树内所有节点信息，插入和删除一个节点信息时间复杂度不高的题。缺点是不能处理动态的树，自带一个 log 导致经常总时间复杂度是两个 log，然后跑得不快。
不过能处理的问题也不算少，泛用性还是有的。而且不难写，细节较少。
原理较为简单。
标签：这个,log,DSU,Tree,儿子,答案,节点,子树内 From： https://www.cnblogs.com/0htoAi/p/16743119.html