$\color{#66ccff}{\texttt{博客食用效果更佳}}$

前言

一次模拟赛的 $T3$ ：传送门

只会 $O(n^2)$ 的我就 $gg$ 了，并且对于题解提供的 $\text{dsu on tree}$ 的做法一脸懵逼。

看网上的其他大佬写的笔记，我自己画图看了一天才看懂（我太蒻了），于是就有了这篇学习笔记。

概念篇/基础运用

算法简介

现在考虑这样一类树上统计问题：

无修改操作，询问允许离线
对子树信息进行统计（链上的信息在某些条件下也可以统计）

树上莫队？点分治？

$\text{dsu on tree}$ 可以把它们吊起来打！

$\text{dsu on tree}$ 运用树剖中的轻重链剖分，将轻边子树信息累加到重链上进行统计，拥有 $O(nlogn)$ 的优秀复杂度，常数还贼TM小，~~你值得拥有！~~

//虽说是dsu on tree，但某个毒瘤@noip说这是静态链分治

//还有其他的数据结构神du仙liu说它可以被看成是静态的树剖（因为其在树上有强大的统计信息的能力，但不能支持修改操作），与正常的树链剖分相对

//所以我同时保留这几种说法，希望数据结构神du仙liu们不要喷我这个juruo

算法实现

遍历所有轻儿子，递归结束时消除它们的贡献
遍历所有重儿子，保留它的贡献
再计算当前子树中所有轻子树的贡献
更新答案
如果当前点是轻儿子，消除当前子树的贡献

那么这里有人可能就要问了，为什么不保留求出的所有答案呢？这样复杂度就更优了啊

如果这样的话，当你处理完一颗子树的信息时，再递归去求解另一颗子树时，

已有的答案就会与当前子树信息相混淆，就会产生错误答案。

所以，从这我们看出，一个节点只能选择一个子节点来保留答案

其它的都要去暴力求解

那么选择哪一个节点能使复杂度最优呢？

显然，我们要尽量均衡答案被保留的子树和不被保存的子树的大小

这是不是就很像树链剖分划分轻重儿子了呢？

人工图解

~~因为窝太蒻了一开始没怎么理解它，所以有了图解这个环节23333。~~

比如现在有一个已经剖好的树（粗边为重边，带红点的是重儿子）：

首先，我们先一直跳轻儿子跳到这个位置：

记录它的答案，并撤销影响，一直往轻儿子上跳

然后发现下一步只能跳到一个重儿子上，就记录他的答案并保存（下文图中被染色的点即为目前保存了答案的点）

接着回溯到父节点上，往下计算答案

因为重儿子保存了答案被标记，往下暴力计算的时候只会经过轻边及轻儿子（即 $6 \rightarrow 12$ 这条边和 $12$ 号节点）

同理， $2$ 号点也可进行类似操作，因为它的重儿子 $6$ 号节点已保存了这颗子树的答案，只需上传即可，

不用再从 $6$ 这个位置再往下走统计答案，唯一会暴力统计答案的只有它的轻儿子 $5$ 号节点

然后继续处理根节点另一个轻儿子 $3$ ，一直到叶子节点收集信息

最后，对根节点的重儿子进行统计，如图，先对箭头所指的两个轻儿子进行计算

接着对每一个重儿子不断保存答案，对轻儿子则暴力统计信息，将答案不断上传

然后，对于根节点的处理同上即可

大致代码：

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$ 道例题

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{-> 树上数颜色 <-}}$ ](https://www.luogu.org/problem/U41492)

此题来自[洛咕日报第 $65$ 篇](https://www.luogu.org/blog/codesonic/dsu-on-tree)作者[ $\text{codesonic}$ ](https://www.luogu.org/space/show?uid=45443)。

我们可以维护一个全局数组 $cnt$ ，代表正在被计算的子树的每种颜色的数量
每次计算子树贡献的时候，把节点信息往里面加就行了，如果一个颜色第一次出现，则颜色种类数 $top++$
对于需要撤销影响的子树，把信息从里面丢出来即可，如果被删除的颜色只有这一个，则颜色种类数 $top--$

$Code$

例题 $2$ ：[ $\color{#66ccff}{\texttt{-> CF600E Lomsat gelral <-}}$ ](https://www.luogu.org/problem/CF600E)

公认的 $\text{dsu on tree}$ 模板题，相比于上题只是增加了对每种数量的颜色和的统计。

我们可以维护 $cnt$ 数组，表示某个颜色出现的次数；再维护一个 $sum$ 数组，表示当前子树出现了 $x$ 次的颜色的编号和
对节点信息统计时，先把它在 $sum$ 数组里的贡献删掉，更新了 $cnt$ 数组后再添回去
然后别忘了开 $long \, long$ （~~血的教训~~）

$Code$

应用篇/各种灵活运用

CF570D Tree Requests

$\color{orange}{\texttt{-> 原题传送门 <-}}$

窝太菜了，不会二进制优化，只会 $O(26*nlogn)$

首先，因为要形成回文串、又可以对字符进行任意排列，所以最多只能有一种字母的出现次数为奇数
然后我们维护一个 $cnt$ 数组，统计每个深度所有字母的出现次数:

cnt[dep[x]][s[x]-'a']+=val;

最后再 $check$ 一下就好了

$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{-> 传送门 <-}}$ ](https://www.luogu.org/problem/P5384)

~~友情提醒：上面这道良心题不仅卡空间，还卡时间（如果你用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$

参考资料/总结

参考资料

总结

以后还会不定期地添加 $\text{dsu on tree}$ 的相关题目~

如果有需要，我会把最后那道题的代码贴出来

dsu on tree学习笔记

前言

概念篇/基础运用

算法简介

算法实现

人工图解

大致代码：

复杂度证明

几道可爱的例题

例题：[](https://www.luogu.org/problem/U41492)

例题：[](https://www.luogu.org/problem/CF600E)

应用篇/各种灵活运用

CF570D Tree Requests

CF246E Blood Cousins Return

CF208E Blood Cousins

IOI2011 Race

NOIP2016 天天爱跑步

[Vani有约会]雨天的尾巴

射手座之日

参考资料/总结

参考资料

总结

例题 $1$ ：[ $\color{#66ccff}{\texttt{-> 树上数颜色 <-}}$ ](https://www.luogu.org/problem/U41492)

例题 $2$ ：[ $\color{#66ccff}{\texttt{-> CF600E Lomsat gelral <-}}$ ](https://www.luogu.org/problem/CF600E)