省流：高级暴力。
首先明确几个概念：
-
重儿子：一个节点体积最大的儿子节点
-
轻儿子：除重儿子之外的儿子节点
树上启发式合并适用于一类无修改子树统计问题。
先看一道例题：CF600E Lomsat gelral
暴力很显然，对每个点遍历子树，统计答案，复杂度 \(O(n^2)\)。
而 DSU on tree 是这么做的：
从根节点开始遍历，遍历到一个点时：
-
先遍历其所有轻儿子，并清空它的统计数组，但保留答案（一定要分清区别）
-
如果不是叶子节点，遍历其重儿子，保留统计数组，保留答案。
-
再遍历轻儿子，将轻儿子信息加到重儿子的统计数组上，直接将答案累计到重儿子答案上，此时答案即为该节点答案。
-
清空轻儿子贡献
代码：
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define debug cout<<"DEBUG"<<endl;
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define imp map<int,int>
using namespace std;
const int N=100005;
int n,h[N],cnt,a[N],siz[N],son[N];
ll ans[N],sum,maxn,t[N];
struct node{
int to,nxt;
}e[N<<1];
void add(int x,int y){
e[++cnt].to=y;
e[cnt].nxt=h[x];
h[x]=cnt;
}
void dfs(int x,int fa){
siz[x]=1;
for(int i=h[x];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa){
dfs(to,x);
if(son[x]==0||siz[to]>siz[son[x]]){
son[x]=to;
}
siz[x]+=siz[to];
}
}
}
void add(int x,int fa,int ds,int d){
t[a[x]]+=d;
if(t[a[x]]>maxn){
maxn=t[a[x]];
sum=0;
}
if(t[a[x]]==maxn){
sum+=a[x];
}
for(int i=h[x];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa&&to!=ds){
add(to,x,ds,d);
}
}
}
void solve(int x,int fa,bool d){
for(int i=h[x];i;i=e[i].nxt){
int to=e[i].to;
if(to!=fa&&to!=son[x]){
solve(to,x,0);
}
}
if(son[x]){
solve(son[x],x,1);
}
add(x,fa,son[x],1);
ans[x]=sum;
if(!d){
add(x,fa,0,-1);//尤其是这里！注意重子树也要清空！因为整个都属于轻子树！
sum=maxn=0;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,1);
solve(1,1,1);
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
return 0;
}
证明一下复杂度：
先证明一个性质：对于每个点，从根节点到它的轻边条数小于 \(\log n\)。
我们设该节点大小为 \(siz\)，轻边条数为 \(x\)，因为轻儿子一定小于二分之一的父节点大小，所以可知 \(siz \leq \dfrac{n}{2^x}\)。
移项可得 \(siz \cdot 2^x\leq n\)
因为 \(siz\) 一定为正，可知 \(2^x\leq n\)，即 \(x \leq \log n\)。
我们知道只有暴力统计轻边时一个点会被计算（去掉遍历的一次），由于轻边条数小于 \(\log n\)，所以只会被重复统计 \(\log n\) 次，所以总复杂度为 \(O(n \log n)\)。
标签：遍历,儿子,int,siz,笔记,son,启发式,树上,节点 From： https://www.cnblogs.com/victoryang-not-found/p/17092334.html