这个算法还是挺人性化的,没有什么难度 就是可能看起来有点晕什么的。
大体 思想是 利用重链刨分来优化子树内部的查询。
考虑一个问题要对每个子树都要询问一次。我们暴力显然是\(n^2\)的。
考虑一下优化这个过程,我们发现儿子的信息可以给父亲用但是不能给兄弟或兄弟里的儿子用。
如果是最大最小值我们只能暴力来搞 但如果是出现次数什么的我们可以利用捅差分来解决这个事情。
考虑我们每次先暴力扫轻儿子然后 再做重儿子然后再把轻儿子的代价加上算当前节点的代价然后再把轻儿子的代价给删掉。
我们发现轻儿子被加上删掉两次 而重儿子只做一次并且保留。
可以发现这样做的复杂度很低 考虑一个点到根有logn条轻边所以这样最坏一个点被暴力来回扫logn次 统计自身答案的时候被扫了1次。
最终复杂度为nlogn 说起来很容易但其实代码还是存在一些细节的 要想好再写。
例题：CF600ELomsat gelral
```
const int MAXN=100010;
int n,len,mx;
int a[MAXN],cnt[MAXN],root[MAXN],sz[MAXN],son[MAXN];
int lin[MAXN],nex[MAXN<<1],ver[MAXN<<1];ll ans[MAXN],w;
inline void add(int x,int y)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
}
inline void dfs(int x,int father)
{
sz[x]=1;
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
if(tn==father)continue;
dfs(tn,x);
sz[x]+=sz[tn];
if(sz[son[x]]<sz[tn])son[x]=tn;
}
}
inline void update(int x,int father,int op,int target)
{
cnt[a[x]]+=op;
if(op>0&&cnt[a[x]]>=mx)
{
if(cnt[a[x]]==mx)w+=a[x];
else w=a[x],mx=cnt[a[x]];
}
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
if(tn==father||tn==target)continue;
update(tn,x,op,target);
}
}
inline void dfs(int x,int father,int op)
{
for(int i=lin[x];i;i=nex[i])
{
int tn=ver[i];
if(tn==father||tn==son[x])continue;
dfs(tn,x,0);//处理轻儿子的答案且清除
}
if(son[x])dfs(son[x],x,1);//处理重儿子的答案
update(x,father,1,son[x]);//把轻儿子的代价加入
ans[x]=w;//答案
if(!op)update(x,father,-1,0),w=0,mx=0;//当前是轻儿子所以删掉
}
int main()
{
freopen("1.in","r",stdin);
n=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<n;++i)
{
int x,y;
x=read();y=read();
add(x,y);add(y,x);
}
dfs(1,0);
dfs(1,0,1);
for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
return 0;
}
···
虽然这道题可以使用线段树合并来做但是那样对空间和时间的花销都是nlogn的 所以dsu on tree在空间上要优于线段树合并。
且 常数上也必然小于线段树合并。