\color{#66ccff}{\texttt{博客食用 效果更佳}}
前言
一次模拟赛的T3：传送门
只会O(n^2)的我就gg了，并且对于题解提供的\text{dsu on tree}的做法一脸懵逼。
看网上的其他大佬写的笔记，我自己画图看了一天才看懂（我太蒻了），于是就有了这篇学习笔记。
概念篇/基础运用
算法简介
现在考虑这样一类树上统计问题：
树上莫队？点分治？
$\text{dsu on tree}$运用树剖中的轻重链剖分，将轻边子树信息累加到重链上进行统计，拥有$O(nlogn)$的优秀复杂度，常数还贼TM小，~~你值得拥有！~~
```cpp
//虽说是dsu on tree，但某个毒瘤@noip说这是静态链分治
//还有其他的数据结构神du仙liu说它可以被看成是静态的树剖（因为其在树上有强大的统计信息的能力，但不能支持修改操作），与正常的树链剖分相对
//所以我同时保留这几种说法，希望数据结构神du仙liu们不要喷我这个juruo
```
## 算法实现
- 遍历所有轻儿子，递归结束时消除它们的贡献
- 遍历所有重儿子，保留它的贡献
- 再计算当前子树中所有轻子树的贡献
- 更新答案
- 如果当前点是轻儿子，消除当前子树的贡献
-----------------------------------------------------------------------------------------------------------------
那么这里有人可能就要问了，为什么不保留求出的所有答案呢？这样复杂度就更优了啊
如果这样的话，当你处理完一颗子树的信息时，再递归去求解另一颗子树时，
已有的答案就会与当前子树信息相混淆，就会产生错误答案。
------------------------------------------------------------------------------------------------------------------
所以，从这我们看出，一个节点只能选择一个子节点来保留答案
其它的都要去暴力求解
那么选择哪一个节点能使复杂度最优呢？
显然，我们要尽量均衡答案被保留的子树和不被保存的子树的大小
这是不是就很像树链剖分划分轻重儿子了呢？
## 人工图解
~~因为窝太蒻了一开始没怎么理解它，所以有了图解这个环节23333。~~
- 比如现在有一个已经剖好的树（粗边为重边，带红点的是重儿子）：
- 首先，我们先一直跳轻儿子跳到这个位置：
- 记录它的答案，并撤销影响，一直往轻儿子上跳
- 然后发现下一步只能跳到一个重儿子上，就记录他的答案并**保存**（下文图中被染色的点即为**目前**保存了答案的点）
- 接着回溯到父节点上，往下计算答案
- 因为重儿子保存了答案被标记，往下暴力计算的时候只会经过轻边及轻儿子（即$6 \rightarrow 12$这条边和$12$号节点）
- 同理，$2$号点也可进行类似操作，因为它的重儿子$6$号节点已保存了这颗子树的答案，只需上传即可，
不用再从$6$这个位置再往下走统计答案，唯一会暴力统计答案的只有它的轻儿子$5$号节点
- 然后继续处理根节点另一个轻儿子$3$，一直到叶子节点收集信息
- 最后，对根节点的重儿子进行统计，如图，先对箭头所指的两个轻儿子进行计算
- 接着对每一个重儿子不断保存答案，对轻儿子则暴力统计信息，将答案不断上传
- 然后，对于根节点的处理同上即可
## 大致代码：
```cpp
inline void calc(int x,int fa,int val)
{
......................
/*
针对不同的问题
采取各种操作
*/
for(rg int i=0;i<(int)G[x].size();++i)
{
int v=G[x][i];
if(vis[v] || v==fa) continue;
calc(v,x,val);
}
}
inline void dfs(int x,int fa,int keep)//keep表示当前是否为重儿子
{
for(int i=0;i<(int)G[x].size();++i)
{
int v=G[x][i].v;
if(v==fa || v==son[x]) continue;
dfs(v,x,0);
}
if(son[x]) dfs(son[x],x,1),vis[son[x]]=true;//标记重儿子
calc(x,fa,1);vis[son[x]]=false;//计算贡献
ans[x]=....;//记录答案
if(!keep) calc(x,fa,-1);//不是重儿子，撤销其影响
}
```
如果是维护路径上的信息，大概还可以这么写：（如果有错，请大佬指出）
ps：关于$\text{dsu on tree}$对路径上信息进行维护的精彩应用，可以看最后$3$道例题
```cpp
inline void dfs(int x,int fa)
{
siz[x]=1,dep[x]=dep[fa]+1,nid[rev[x]=++idx]=x;
//再次借助树剖的思想，子树内节点顺序转为线性
for(rg int i=0;i<(int)G[x].size();++i)
{
int v=G[x][i].v,w=G[x][i].w;
if(v==fa) continue;
dfs(v,x),siz[x]+=siz[v];
if(!son[x] || siz[v]>siz[son[x]]) son[x]=v;
}
}
inline void calc(int x,int val)
{//对x这一节点进行单独处理
if(val>0) //计算贡献
else //撤销影响
}
inline void dfs2(int x,int fa,int keep)
{
for(rg int i=0;i<(int)G[x].size();++i)
{
int v=G[x][i].v;
if(v==fa || v==son[x]) continue;
dfs2(v,x,0);
}
if(son[x]) dfs2(son[x],x,1);
for(rg int i=0;i<(int)G[x].size();++i)
{
int v=G[x][i].v;
if(v==fa || v==son[x]) continue;
for(rg int j=0;j<siz[v];++j)
{
int vv=nid[rev[v]+j];
..........
//更新答案
}
for(rg int j=0;j<siz[v];++j) calc(nid[rev[v]+j],1);
}
calc(x,1);
..........//更新答案
if(!keep) for(rg int i=0;i<siz[x];++i) calc(nid[rev[x]+i],-1);
}
```
## 复杂度证明
不感兴趣的大佬可以跳过这一段。（蒟蒻自己乱$yy$的证明，如果有错请大佬指出）
- 显然，根据上面的图解，一个点只有在它到根节点的路径上遇到一条轻边的时候，自己的信息才会被祖先节点暴力统计一遍
- 而根据树剖相关理论，每个点到根的路径上有$logn$条轻边和$logn$条重链
- 即一个点的信息只会上传$logn$次
- 如果一个点的信息修改是$O(1)$的，那么总复杂度就是$O(nlogn)
几道可爱的例题
例题1：\color{#66ccff}{\texttt{-> 树上数颜色 <-}}
此题来自洛咕日报第65篇作者\text{codesonic}。
-
我们可以维护一个全局数组cnt，代表正在被计算的子树的每种颜色的数量
-
每次计算子树贡献的时候，把节点信息往里面加就行了，如果一个颜色第一次出现，则颜色种类数top++
-
对于需要撤销影响的子树，把信息从里面丢出来即可，如果被删除的颜色只有这一个，则颜色种类数top--
Code
例题2：\color{#66ccff}{\texttt{-> CF600E Lomsat gelral <-}}
公认的\text{dsu on tree}模板题，相比于上题只是增加了对每种数量的颜色和的统计。
Code
应用篇/各种灵活运用
CF570D Tree Requests
\color{orange}{\texttt{-> 原题传送门 <-}}
窝太菜了，不会二进制优化，只会O(26*nlogn)
cnt[dep[x]][s[x]-'a']+=val;
Code
CF246E Blood Cousins Return
\color{orange}{\texttt{-> 原题传送门 <-}}
-
首先用map把给的所有名字哈希成1到n的数字
-
题目就可以转化为求出每个深度有多少不同的数
-
同样，对每个深度开个set去重并统计
-
然后就是套板子的事情了
Code
CF208E Blood Cousins
\color{orange}{\texttt{-> 原题传送门 <-}}
-
显然原问题可以转化为求该点的k级祖先有多少个k级儿子（如果没有k级祖先，答案就是0）
-
而一个点x的k级儿子即为在以x为根节点的子树中有多少点的dep为dep[x] + k
-
把所有询问读进来，求出相关的点的k级祖先（可以离线O(n)处理，也可以倍增O(nlogn)搞；如果时空限制比较紧，就采取前者吧)
-
然后因为是统计节点数，所以开一个普通的cnt数组维护即可。最后答案别忘了-1，因为算了自己
扔一个加强版的（N \le 10^6，128MB,1s）：\color{#66ccff}{\texttt{-> 传送门 <-}}
友情提醒：上面这道良心题不仅卡空间，还卡时间（如果你用dsu on tree）
Code
IOI2011 Race
\color{orange}{\texttt{-> 原题传送门 <-}}
点分治的题怎么能用点分治呢？而且这还是dsu on tree学习笔记
-
首先，这道题是对链的信息进行统计，就不能再像对子树的统计方法去搞♂了，所以需要一些奇技淫巧
-
思路与点分治一样，对于每个节点x，统计经过x的路径的信息
-
注意到这道题链上的信息是可加减的，所以我们可以不保存x的子孙\rightarrow x的信息，而是保存每个节点到根节点的信息，在统计的时候在减去x \rightarrow根节点的信息
-
然后我们考虑如何统计，我们可以在每个节点维护一个桶cnt，记录从这个点x往下走的所有路径中，能形成的每种路径权值和以及其所需要的最少的边的数量：
-
对于v_{ij}，计算出其到x的距离dis及深度差d(可以看成路径上的节点数)，并用d + cnt[k−dis]来更新答案。
-
然后用刚才得到的dis对应的d来更新cnt[dis]的值。
-
这样就相当于，用每个v_{ij}到x的链，与之前桶中所保存某条链的路径权值和之和恰为k的拼成一条路径，并更新答案。然后，再把它也加入桶中
-
再套上\text{dsu on tree}的板子，每个节点保存它的重儿子的 桶的信息即可
虽然是O(nlog^2n)的，但常数小，咱不慌
但是窝太菜了，用map作桶不开O2会T \, 3个点（毕竟用了STL，还有两只log），有空再重写一遍233
貌似用unodered_{}map不开O2也卡得过去。。
Code
NOIP2016 天天爱跑步
\color{orange}{\texttt{-> 原题传送门 <-}}
- 首先，我们可以把S \Rightarrow T这条路径拆成S \rightarrow lca(S,T) 和 lca(S,T) \rightarrow T两段来考虑
-
考虑在第一段路径上一点u能观测到该玩家的条件是：dep[S] - dep[u] = w[u]
-
同理，在第二段路径上一点u能观测到该玩家的条件是：dep[T] - dep[u] = dis(S,T) - w[u]，即dep[S] - 2 \times dep[lca(S,T)] = w[u] - dep[u]
-
然后可以用差分的思想，对每个节点开两个桶up、down进行统计
-
在S的up中插入dep[S]
-
在T的down中插入dep[S] - 2 \times dep[lca(S,T)]
-
因为lca(S,T)会对S \rightarrow T和T \rightarrow S都进行统计，所以在其up中删除dep[S]
-
同理，在fa[lca(S,T)]的down中删除dep[S] - 2 \times dep[lca(S,T)]
-
然后用\text{dsu on tree}统计即可，答案为up[w[u]+dep[u]] + down[w[u] - dep[u]]
注意到w[u] - dep[u]可能小于零，为了避免负数下标、又不想套map，我们可以使用如下trick
int up[N],CNT[N<<1],*down=&CNT[N];
//把donw[0]指向CNT[N]，这样就可以给负数和正数都分配大小为N的空间
跑的虽然没有普通的差分快，不过吊打线段树合并还是绰绰有余的
Code
[Vani有约会]雨天的尾巴
\color{orange}{\texttt{-> 原题传送门 <-}}
跟天天爱跑步差不多，就不画图了（~懒）
O(nlog^2n)$，常数应该和树剖差不多，不过因为每个点都要进行增加删除两个操作，常数大了一倍，而且还用了线段树，所以$\cdots
不过依然比部分线段树合并跑的快2333
Code
由以上三题，我们可以看出，在一定条件下，\text{dsu on tree}也是可以在链上搞♂事情的
比如Race满足链上信息可加减性，后两道题可以用差分将链上的修改/询问转化为点上的修改/询问
但\text{dsu on tree}可以应用的条件肯定不止以上两种，因为窝太蒻了，只见识了这些题，以后看到其他类型的也会补上来
射手座之日
\color{orange}{\texttt{-> 提交地址 <-}}
现在终于可以回过头来解决这个题了
留给大家思考吧，要代码的话可以私信我
虽然有很多大佬会线段树合并或虚树上dp秒切这道题，不过还是希望用dsu \; AC
参考资料/总结
参考资料
-
CF一位大神的blog
-
Melantha的blog
-
ctz＇s blog
-
candy?的blog
-
zlttttt的blog
总结
以后还会不定期地添加\text{dsu on tree}的相关题目~
如果有需要，我会把最后那道题的代码贴出来