dsu on tree 学习笔记

\(\text{dsu on tree}\)（树上启发式合并）是用于统计子树信息的算法。

基于CF上Arpa的那套理论

​

常数小，代码易写，于是学习了一下

前置技能

• 树链剖分-重链剖分
  • 重链/轻链的复杂度

思想

\(\text{dsu on tree}\)依赖于轻重链划分

其思想是：只保留重子树的信息给祖先再利用

算法流程

\(\text{dsu on tree}\)的过程可以如下描述：

1. 处理轻子树的答案
2. 处理重子树的答案，并保留贡献
3. 获取轻子树对答案的贡献，得到当前点的答案
4. 如果当前点是轻儿子，去除当前点的贡献

伪代码如下：

void change(int x,int w){
	记录x的贡献
	for (int j=lnk[x];j;j=nxt[j])
	 if (!xH[son[j]]) change(son[j],w);
}
void dsu(int x,bool keep){
    for 每个轻儿子 dsu(son,0);
	dsu(H_son[x],1); xH[H_son[x]]=1;
	change(x,1); xH[H_son[x]]=0;
    更新x的答案
	if (!keep) change(x,-1);
}

复杂度分析

这样的做法看似很暴力，其实有理有据

考虑change带来的复杂度：

只有轻儿子才会把子树信息加入父节点

重链剖分把任意根到叶子路径划分成了不超过\(logn\)条轻边和\(logn\)条重链

每个点到根路径都有不超过\(logn\)条轻边

也就是说，每个点被change了\(logn\)次

所以总复杂度是\(O(n+nlogn)\)的

例题

Codeforces 600E

Codeforces 570D