树上启发式合并（DSU on tree），和莫队一样都是暴力美学，用于解决一些树上离线问题，尤其是指“对于每个节点，询问关于子树的信息”这类问题。而且虽然是暴力做法，但是时间复杂度神奇的来到了 \(O(nlogn)\) 。
启发式合并
启发式合并是一种思想，在合并两个集合时，优先将小集合合并到大集合中去。这样就能保证合并的总时间复杂度在nlogn以内。
树上启发式合并
对于树上维护的信息，需要将子节点维护的信息全部合并到父亲节点中。但是无论是时间复杂度还是空间复杂度都不允许我们在每一个节点都维护一个数据结构，因此需要实现资源的“复用”（引用Pecco大神说法）。轻儿子只统计自己内部答案，因此求完贡献以后需要将贡献删去；重儿子统计完答案后不会将贡献删除，因此实现了资源的“复用”。（更加简单的说法就是，每次都将轻儿子合并到重儿子中）
具体实现：
-
先将整颗树进行轻重链剖分，重儿子相当于一个大集合，我们在合并的过程中都是轻儿子不断的和重儿子合并。
-
我们用一个全局变量记录答案和要维护的值，每次合并完都直接记录答案，是离线算法。
-
每次递归先进入轻儿子，因为轻儿子只负责自己内部的统计，因此轻儿子所统计的结果要全部删掉。
-
轻儿子统计完后，统计重儿子。重儿子的结果在统计完后不删除保留，因为此时轻儿子们已经都算完了，没有用了，我们直接遍历所有轻儿子的所有子树，子树对应的是一段区间，直接将这些儿子合并。
-
统计答案，再判断u节点是来自于轻边还是重边，是轻边要记得删掉以u为子树的所有信息。
维护此时字数上出现最大颜色的次数与颜色总类型数，如果两者相乘等于子节点数则说明各种颜色出现次数相等。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define endl '\n'
const int N=2e5+5;
vector<int>g[N];
//子树大小与重儿子编号
int siz[N],son[N];
//dfs序
int l[N],r[N],id[N],rnk[N],tot;
void dfs1(int u,int f)
{
l[u]=id[u]=++tot;
rnk[tot]=u;
siz[u]=1;
for(auto v:g[u])
{
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
}
r[u]=tot;
}
int w[N],ans;
int col[N],maxx,num,cn[N];
void add(int u)
{
u=w[u];
if(col[u]==0) num++;
cn[col[u]]--;
col[u]++;
maxx=max(col[u],maxx);
cn[col[u]]++;
}
void del(int u)
{
u=w[u];
cn[col[u]]--;
if(cn[col[u]]==0) maxx=col[u]-1;
col[u]--;
if(col[u]==0) num--;
cn[col[u]]++;
}
void dfs2(int u,int f,int keep)
{
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
dfs2(v,u,0); //先计算轻儿子的答案
}
if(son[u]) dfs2(son[u],u,1); //重儿子贡献保留
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
for(int i=l[v];i<=r[v];i++) {
add(rnk[i]); //添加轻的贡献儿子
}
}
add(u);
if(maxx*num==siz[u]) ans++;
if(keep==0) {
for(int i=l[u];i<=r[u];i++) {
del(rnk[i]);
}
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int f;cin>>w[i]>>f;
g[f].push_back(i),g[i].push_back(f);
}
dfs1(1,0);
dfs2(1,0,0);
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;//cin>>T;
while(T--) solve();
return 0;
}
考虑将一个节点 \(j\) 添加进一堆已有的点中，贡献变化。
对于所有小于该点点权的贡献和 \(\sum_{w_{p}< w_{j}}w_{j}\times(w_{j}-w_{p})=k\times w_{j}^{2}-w_{j}\times\sum_{w_{p}< w_{j}}w_{p}\) ；
对于所有大于该点点权的贡献和 $\sum_{w_{p}> w_{j}}w_{p}\times(w_{p}-w_{j})=\sum_{w_{p}> w_{j}}w_{p}^{2}-w_{j}\times\sum_{w_{p}> w_{j}}w_{p} $ 。
小于该数个数、前缀和、后缀和、后缀平方和的修改与查询都可以通过维护树状数组实现，总时间复杂度 \(O(nlog^{2}n)\) 。
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define endl '\n'
const int N=5e5+5;
const int M=1e6;
struct BIT
{
int t[M+6];
int lowbit(int x) { return x&(-x); }
//单点修改
void update(int pos,int k) {
for(int i=pos;i<=M;i+=lowbit(i)) t[i]+=k;
}
//区间查询
int ask(int pos) {
int ans=0;
for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
return ans;
}
}B[3];
vector<int>g[N];
//子树大小与重儿子编号
int siz[N],son[N];
//dfs序
int l[N],r[N],id[N],y[N],tot;
void dfs1(int u,int f)
{
l[u]=id[u]=++tot;
y[tot]=u;
siz[u]=1;
for(auto v:g[u])
{
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
}
r[u]=tot;
}
int w[N],ans,res[N];
void col(int u,int op)
{
int num=B[0].ask(w[u]),sum=B[1].ask(w[u]);
ans+=op*(w[u]*w[u]*num-w[u]*sum)*2;
int bsum=B[1].ask(M)-B[1].ask(w[u]),bpf=B[2].ask(M)-B[2].ask(w[u]);
ans+=op*(bpf-bsum*w[u])*2;
B[0].update(w[u],op*1);
B[1].update(w[u],op*w[u]);
B[2].update(w[u],op*w[u]*w[u]);
}
void add(int u) { col(u,1); }
void del(int u) { col(u,-1); }
void dfs2(int u,int f,int keep)
{
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
dfs2(v,u,0); //先计算轻儿子的答案
}
if(son[u]) dfs2(son[u],u,1); //重儿子贡献保留
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
for(int i=l[v];i<=r[v];i++) {
add(y[i]); //添加轻的贡献儿子
}
}
add(u);
res[u]=ans;
if(keep==0) {
for(int i=l[u];i<=r[u];i++) {
del(y[i]);
}
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>w[i];
int ret=0;
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++) ret^=res[i];
cout<<ret<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;//cin>>T;
while(T--) solve();
return 0;
}