dsu on tree 学习笔记
wing_heart
·
·
算法·理论
树上启发式合并
原文
dsu on tree 主要可以解决一些静态的子树信息查询的问题，当然也可以拓展到路径，最常见的套路就是强制该路径经过当前子树根节点。
启发式算法是基于人类的经验和直观感觉，对一些算法的优化。——来自 OI Wiki
简单来说，树上启发式合并就是合并子树信息时，直接继承重儿子的信息，然后暴力遍历轻儿子的子树合并信息。
主要使用场景是：每个子树都开空间记忆化信息会 MLE，每个子树都重新遍历一遍信息会 TLE。
最基础的 dsu on tree，时间复杂度是 O(n \log n)，空间复杂度是 O(n)。
e.g. 并查集启发式合并
相信你一定知道并查集的按秩合并：将深度小的并查集合并到深度大的并查集。
这样可以保证并查集树高是 \log n 级别的。
code
void merge(int x, int y) {
int xx = find(x), yy = find(y);
if (size[xx] < size[yy]) swap(xx, yy);
fa[yy] = xx;
size[xx] += size[yy];
}
——来自 OI Wiki
那么什么是 dsu on tree 呢？
模板题
树上数颜色
给出一棵 n 个节点以 1 为根的树，节点 u 的颜色为 c_u ，有 m 次询问，每次给出结点 u 询问 u 子树里一共出现了多少种不同的颜色。
对于所有数据，有 1\le m,c_i\le n\le 10^5
暴力算法 O(nm)
每次询问遍历 u 的整棵子树。会超时。
树上莫队 O(n\sqrt n)
我不会。
dsu on tree O(n\log n)
今天的正题来啦~！
很简单的，几句话就讲完了。
考虑离线询问，预处理出答案后 O(1) 回答每个询问。
因此我们只用桶存储**重儿子**（在本题为 $size$ 最大的儿子）的信息，然后暴力地遍历轻儿子的子树，将答案加到桶中。
实际实现可以先搜轻儿子，然后把桶清空。然后搜重儿子，不清空桶。然后处理自身。
对于点 $u$，搜索的具体的步骤：
1. 搜轻儿子，然后清空桶。
2. 搜重儿子，不清空桶。
3. 把 $u$ 的贡献加到桶里。
总时间复杂度 $O(n \log n)$。
-----------
时空复杂度证明：
预处理重儿子时间复杂度是 $O(n)$。
一个桶的空间是 $O(n)$。我们从始至终都是用这一个桶就够了。
轻儿子 $v$ 的子树大小小于 $u$ 子树大小的一半，即 $siz_v < \frac{siz_u}{2}$。
所以递归轻儿子最多 $\log n$ 层子树大小就为 $0$ 了。
一个点 $u$ 会被它的某些祖先暴力遍历轻儿子的子树时候搜到。
因为轻儿子 $v$ 的子树大小小于 $u$ 子树大小的一半，所以它只有至多 $\log n$ 个祖先会暴力遍历它所在的子树。所以 $u$ 至多被暴力搜 $\log n$ 次。所以总时间复杂度是 $O(n \log n)$ 的。
### Code
```cpp
#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int n,c[N];
int m,u;
int v;
int sum[N];//每棵子树的不同颜色数
vector<int> son[N];
int siz[N],cnt[N];// cnt为桶
int gson[N];// 重儿子
int tot;// 当前不同颜色数
void dfs(int u,int fa){
siz[u]=1;
for(int v:son[u]){
if(v==fa) continue;
siz[u]+=siz[v];
if(siz[v]>siz[gson[u]]) gson[u]=v;
}
}
void add(int c) {if(!cnt[c]++) tot++;}
void del(int c) {if(!--cnt[c]) tot--;}
void change(int u,int fa,bool k){//k 表示加入或删除
if(k) add(c[u]);
else del(c[u]);
for(int v:son[u]){
if(v==fa) continue;
change(v,u,k);
}
}
void dsu(int u,int fa,bool k){// k 表示是否保留桶的信息
for(int v:son[u]){// 计算轻儿子答案，算完删除桶
if(v==fa||v==gson[u]) continue;
dsu(v,u,0);
}
if(gson[u]) dsu(gson[u],u,1);// 计算重儿子答案，算完保留桶
add(c[u]); // 加入 u 的贡献
for(int v:son[u]){//暴力遍历合并轻儿子答案
if(v==fa||v==gson[u]) continue;
change(v,u,1);// 遍历整棵轻子树，复杂度 O(siz_v)
}
sum[u]=tot;//记录答案
if(!k) change(u,fa,0);//清空桶（注意时间复杂度需要为 O(siz_u)，直接 memset 会超时）
}
int main(){
sf("%d",&n);
for(int i=1;i<n;i++){
sf("%d%d",&u,&v);
son[u].push_back(v),son[v].push_back(u);
}
for(int i=1;i<=n;i++){
sf("%d",&c[i]);//颜色
}
dfs(1,0);//找重儿子，O(n)
dsu(1,0,0);
sf("%d",&m);
for(int i=1;i<=m;i++){
sf("%d",&u);
pf("%d\n",sum[u]);
}
}
```
## 一点题目
[点分治模板](https://www.luogu.com.cn/problem/P3806)
[点分治习题 Tree](https://www.luogu.com.cn/problem/P4178)
以上两题都可以用 dsu on tree 由处理子树问题扩展到处理路径问题解决。
即处理 $u$ 时，计算 $u$ 子树内经过 $u$ 的路径的答案。
具体做法参考题解。
[XOR Tree](https://www.luogu.com.cn/problem/CF1709E)
容易发现，如果可以更改 $a_i$，则所有经过 $i$ 的路径权值 $d$ 都一定不为 $0$（将 $a_i$ 改为极大的数即可）。
考虑深搜解决，也就是说，处理 $u$ 时，$u$ 的子树已处理完毕。
对于 $d(u,v)=0$，更改 $\text{lca}(u,v)$ 一定是最优的，证明如下：
若 $(u,lca)$ 上有一点 $k$，存在一条经过 $k$ 权值为 $0$ 的路径 $(l,r)$，其中 $r$ 为 $l$ 的祖先，那么 $(l,r)$ 必定经过 $lca$，否则该路径已经处理过了，$d(l,r)\neq 0$。
因此更改 $k$ 是不优的，更改 $lca$ 的祖先无法更改到 $(u,v)$。
因此更改 $lca$ 是最好的。
首先预处理出每个结点到根的路径权值，即 $d_u$，方便后面计算。
然后我们对每个点开一个 set，储存他的子树内所有点到根节点的权值。
考虑启发式合并，每个结点继承 $set_{size}$ 最大的儿子的 $set$，然后暴力枚举合并其他儿子。
写法上有很多种，比如可以这么写：
```cpp
set<int> s[N];
// 下面是函数 dsu 的部分代码
dsu(v,u);
if(s[v].size()>s[u].size()) swap(s[u],s[v]);// 更新重儿子
for(int x:s[v]) if(s[u].find(x^a[u])!=s[u].end()) k=1; // k 是用来判断是否要清空 set
for(int x:s[v]) s[u].insert(x); // 启发式合并重儿子
```
计算答案只需在 $set$ 里使用 $find$ 函数查询是否存在值 $d_x \oplus a_u$，若存在，则点 $u$ 需要更改，答案 $+1$，同时清空 $set_u$。
复杂度因为有 set，是两只 $\log$ 的，但是 dsu 常数实在是很小。
[P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并](https://www.luogu.com.cn/problem/P4556) ~~线段树合并板子当然要用可爱的 dsu on tree 做啦~~因为维护最大值需要再开一个数据结构维护，我使用了常数较小的 priority_queue，时间比线段树合并多一个 $\log$，是 $O(n \log^2 n)$ 的，但是可能因为可爱的 dsu 的优秀常数~~应该说是因为人见人爱花见花开的线段树的巨大常数导致~~在没有优化常数的情况下甚至也可以吊打线段树合并。