dsu on tree（树上启发式合并）

dsu的意思是并查集，但是dsu on tree这个算法和并查集的关系也就剩一个启发式合并了。

学习这个算法的切入点还真不在启发式合并，关于启发式合并的问题实际上是最后再考虑它为什么叫启发式合并。

我们选什么作为切入点呢，选莫队算法，如果你不懂莫队也没关系，这里只是说这两个算法在应用的场景上面有共通点，只不过一个应用于子树，一个应用于数组区间。

莫队

我们从最简单的区间问题“子区间的静态求和问题”开始讨论好了。

假定现在有一个数组a，数组里面有若干个元素，然后你已知 $[l_1,r_1]$ 这段区间的区间和，假设区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 有大面积重合，重合率达到90%。问你如何在已知 $[l_1,r_1]$ 区间和的情况下计算 $[l_2,r_2]$ 的区间和？

那只要把 $l_1$ 向后面移动，然后令 $\,ans\,$ 每次减少便利到的数组元素 $a[l_1]$ ，再把 $r_1$ 向后移动，每次加入新的元素 $a[r_1]$ 。

这样利用区间 $[l_1,r_1]$ 计算区间 $[l_2,r_2]$ 的结果复杂度为 $|l_2-l_1|+|r_2-r_1|$ ，在区间重合率较高的情况下可以优化很多重复计算。

假设共有m个查询问题，我每一次的查询都基于上一次查询的结果基础上，那么我的总复杂度就可以表示为

$\sum_{i=1}^{m}{|l_i-l_{i-1}|+|r_i-r_{i-1}|}$ (其中 $l_0=r_0=0$ )

如果我想要让这个复杂度最小化，也就是“如何安排一个合理的查询顺序，使得复杂度最小化”。

那我这片博客不是讲莫队，所以不解答“合理的查询顺序”是个怎样的顺序。

考虑这个算法和传统的暴力算法相比，优势在什么地方？，自然就是“如果相邻查询之间有大面积重合，那么就算的飞快”这个优势。

“查询之间有大面积重合”换个说法就是有大量的重复子问题。

与动态规划的思路不同，动态规划的思想是既然有重复子问题，那我就不停地划分子问题，然后分阶段求解不同子问题，最终求的答案，这样最高效率的利用了重复子问题。

而莫队是如何利用重复子问题的呢，显然它没有保存，它只是因为当前的查询与下一个查询之间有重复部分，所以不用重复统计仅此而已。

总之就是，我们从莫队上面得到了启示：对于静态的查询类问题，如果查询之间有大面积的重合，那么我只要安排一个合理的顺序暴力求解就能够降低复杂度。

为什么不用区间DP/倍增跳表或者线段树维护

就是因为它们做不到，所以才需要莫队的啊，要么是时空不允许，要么就干脆不满足区间合并的性质。

比如“区间元素种类数”，“区间出现次数>k的元素”等。

这个问题的答案也揭示了后面“为什么需要dsu on tree，而非直接树形DP”这个问题。

dsu on tree

先给你这么一棵树，根节点是1号节点有n-1条有向边链接，假设每个点有点权，第i个点的权值为 $val\left[ i \right]$ 。我进行若干次查询，每次查询以某点为根所表示的子树权值和。

我统计权值和所用的代码如下：

int ans;
bool vis[MAXN];
void init()
{
    ans=0;
    memsest(vis,false,sizeof(vis));
}
void dfs(int x)
{
    if(vis[x])return;
    vis[x]=true;
    ++ans;
    for(auto &i:G[x])
    {
        dfs(i);
    }
}

假设我要查询节点{1,4}的权值和，在不改变算法的情况下，如何降低复杂度？

那无非就是两种方法：

先查1，再查4

dfs(1);
init();
dfs(4);

先查4，再查1

dfs(4);
dfs(1);

先不讨论init的时间消耗，假设init函数不消耗时间，在这个情况下谁更优？

显然是第二个嘛，因为第一种方案的复杂度为 $O\left( size(1)+size(4) \right)$ ，第二种方案复杂度只剩下 $O\left( size(1) \right)$ 了。

这个优化很明显，太过分了，因为相当于dfs(4)白嫖了变成 $O\left( 1 \right)$ ，甚至不用计算复杂度。

为什么会出现这个现象呢，因为dfs(4)就是dfs(1)的子问题，那就相当于“重合率100%”，我可以节约100%的时间。

ok，我们现在来切入正题：假设我全查了，如何安排顺序使得复杂度最小化（同样假设init函数不消耗时间）？

dfs(5);
dfs(3);
init();
dfs(7);
init();
dfs(6);
dfs(4);
dfs(2);
dfs(1);

那这个查询顺序是怎么来的呢？

情景一：单链

那这个是最简单的，只要按照dfs(n),dfs(n-1)....dfs(1)的顺序执行即可。

情景二：分叉

由情景一，我们已经知道了，在最优顺序里面，一定是先dfs,x,y,z这三个子节点之后再进行dfs(rt)。

换句话说rt对于x,y,z的顺序已经定了一定是rt在后，只需要对xyz进行排序即可。

我们发现，dfs(x),dfs(y),dfs(z)这三个函数没有任何交集，换句话说就是根本没有重复子问题。

那么无论先处理谁，只要后面需要调用dfs(x),dfs(y),dfs(z)中的任意一个，都必须推倒重来，执行一次init()。

因为接下来会调用dfs(rt)，反倒是谁最后被执行，谁就可以被保留不计算复杂度。

那也就是说

dfs(y);init();dfs(z)init;dfs(x);dfs(rt);

dfs(z);init();dfs(y)init;dfs(x);dfs(rt);

这两个求解顺序都是复杂度最低的求解顺序。

总结一下

1、优先处理子树查询，再处理根节点

2、当出现多个子树的时候，优先处理子树尺寸较小的子树，然后使用init清空，最后处理尺寸最大的子树，然后保留信息的情况下处理根节点。

看到这里的话你肯定发现了，所谓“尺寸最大的子树”的子树，它也就是轻重树链剖分中“重儿子”的概念，而“子树尺寸较小”则是轻儿子。

再次总结一下

1、优先处理子树查询，再处理根节点。

2、当出现多个子树的时候，优先处理轻儿子，处理完每个轻儿子之后使用init清空，最后处理重儿子并保留信息的情况下处理根节点。

现在再反过来看一开始提出的例题

最优求解顺序：

dfs(5);
dfs(3);
init();
dfs(7); 
init();
dfs(6);
dfs(4);
dfs(2);
dfs(1); 
//init();

1~2~4~6是一条重链，链首是1

3~5是一条重链，链首是3

7是一条重链，链首是7

“最优求解序列”就是轻重树链剖分的dfs序列的倒置，并且在每条重链的链首处进行了一次init()

那么“最优求解序列”究竟效率如何呢？

为了解决这个问题，还是要借助树链剖分。

定理：树上任意节点到根节点的简单路径中，经过轻边的数目不多于 $log_2n$ 。

我们知道，对于任意一个节点x，我们需要统计它的信息仅当调用dfs(y)，y是x的祖先时。

那么只要求出所有的dfs(y)中遍历x的次数，把它们加起来也就是这个算法的最终复杂度。

因为y是x的祖先，所以dfs(y)时只要之前调用过init函数，x就必须要重新统计。

换句话说只要统计dfs(y)时init的调用次数即可。

因为只有在链首处才会调用init，所以这个问题的答案就等于从x到根节点的简单路径中，经过轻边的数目。

那对于任意节点x，它对总时间复杂度的贡献不多于 $log_2n$ ，那么这个算法的最终复杂度就不多于 $O(nlog_2n)$

代码讲解

例题：输入一个正整数n表示有n个节点的树，根节点为1号节点，然后输入n个正整数表示点权，请输出n个数，以每个点为根的子树权值和。

首先是“如何求出最优求解序列”，前面也说了，这个东西就是“树链剖分dfs序的倒序”，翻转一个序列最简单的方法就是压到栈里面再输出，我们知道递归算法是一个天然的堆栈。所以我们只要利用dfs按照树链剖分的规则再来一遍，然后在return之前求解即可。

那因为我们需要用到树链剖分的dfs序嘛，那肯定是要真的树剖一下，我们做一下树剖然后记录一些信息。

int sz[MAXN],deep[MAXN],fa[MAXN],son[MAXN],L[MAXN],R[MAXN],Index[MAXN],dfn;
void dfs(int x,int dep,int father)
{
    sz[x]=1;
    deep[x]=dep;
    fa[x]=father;
    son[x]=0;
    L[x]=++dfn;
    Index[dfn]=x;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,dep+1,x);
            sz[x]+=sz[e[i].to];
            if(!son[x]||sz[son[x]]<sz[e[i].to])son[x]=e[i].to;
        }
    }
    R[x]=dfn;
    return;
}

$sz\left[ x \right]$ 表示子树尺寸， $deep\left[ x \right]$ 表示当前节点深度, $fa\left[ x \right]$ 表示父节点， $son\left[ x \right]$ 表示重儿子

$L\left[ x \right]$ , $R\left[ x \right]$ 表示x节点所表示子树中dfn的最小值与最大值。并且x节点所表示子树中dfn的最小值就是x节点的dfn，即 $id\left[ x \right]=L\left[ x \right]$ 。

$Index\left[ x \right]$ 是 $id\left[ x \right]$ 的逆数组。

$id\left[ x \right]$ 表示“节点x的dfn是多少”（由于在数值上等于 $L\left[ x \right]$ ，所以代码中用 $L\left[ x \right]$ 代替了 $id\left[ x \right]$ ）

$Index\left[ x \right]$ 表示“ dfn为x的节点是哪个节点”

这里其实是做了树链剖分的一半工作（即只有树链剖分中dfs1的部分），当然你也可以做一个完整的链剖把 $top\left[ x \right]$ (表示重链链首)也给求出来。

有了链剖预处理出来的各种dfs序，接下来是代码的主体部分

先递归轻儿子，每次递归完轻儿子（当前节点是重链的链首）时全部清0。然后递归重儿子并且不清空，最后dfs(x)并且跳过重儿子。

void dsu(int x,bool del)
{
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]||e[i].to==son[x])continue;
        dsu(e[i].to,true);
    }
    ///skip the heavy son
    if(son[x])
    {
        dsu(son[x],false);
        skp=son[x];
    }
    ///get data from light son and itself
    get_data(x);
    ///solve problem with subtree x
    ans[x]=sum;
    ///if delete clear all
    if(del)
    {
        skp=0;
        sum=0;
    }
    return;
}

这里额外提一句，如果你之前做了完整的树剖，那么del这个参数可以不传，只需要把if(del)改写为if(x==top[x])这个条件即可。（重链的链首处进行init）

这个get_data()函数，就是我一开始举例时的"dfs暴力统计子树权值和，并且碰到vis就return"的那个函数

void get_data(int x)
{
    if(x==skp)return;   //if(vis[x])return;
    sum+=val[x];
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x])continue;
        get_data(e[i].to);
    }
}

当然，因为有了dfs序列，我们预处理了 $L\left[ x \right]$ , $R\left[ x \right]$ ，这里可以使用非递归的for循环写法

void get_data(int x)
{
    for(int i=L[x];i<=R[x];++i)
    {
        if(Index[i]==skp)
        {
            i=R[Index[i]];
            continue;
        }
        sum+=val[Index[i]];
    }
}

这样这道题就写完了

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n;
int g[MAXN],tot,dfn,u,v;
int sz[MAXN],deep[MAXN],fa[MAXN],son[MAXN],L[MAXN],R[MAXN],Index[MAXN],skp;
long long sum,ans[MAXN],val[MAXN];
struct edges
{
    int to,next;
}e[2*MAXN];
void add_edge(int from,int to)
{
    e[++tot].to=to;
    e[tot].next=g[from];
    g[from]=tot;
    return;
}
void dfs(int x,int dep,int father)
{
    sz[x]=1;
    deep[x]=dep;
    fa[x]=father;
    son[x]=0;
    L[x]=++dfn;
    Index[dfn]=x;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,dep+1,x);
            sz[x]+=sz[e[i].to];
            if(!son[x]||sz[son[x]]<sz[e[i].to])son[x]=e[i].to;
        }
    }
    R[x]=dfn;
    return;
}
void get_data(int x)
{
    for(int i=L[x];i<=R[x];++i)
    {
        if(Index[i]==skp)
        {
            i=R[Index[i]];
            continue;
        }
        sum+=val[Index[i]];
    }
}
/*
void get_data(int x)
{
    if(x==skp)return;
    sum+=val[x];
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x])continue;
        get_data(e[i].to);
    }
}
*/
void dsu(int x,bool del)
{
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]||e[i].to==son[x])continue;
        dsu(e[i].to,true);
    }
    ///skip the heavy son
    if(son[x])
    {
        dsu(son[x],false);
        skp=son[x];
    }
    ///get data from light son and itself
    get_data(x);
    ///solve problem with subtree x
    ans[x]=sum;
    ///if delete clear all
    if(del)
    {
        skp=0;
        sum=0;
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&val[i]);
    }
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,1,-1);
    dsu(1,0);
    for(int i=1;i<=n;++i)
    {
        printf("%lld%c",ans[i],i==n?'\n':' ');
    }
    return 0;
}

为什么需要dsu on tree

这个问题其实就类似使用莫队的困境一样，有的树形dp，它压根就不支持子树之间的合并问题。就是说虽然根节点可以快速在单链时快速转移，但是碰到两个以上的子树时，两子树之间的信息不能快速合并。

例如“子树元素种类数”，“子树元素众数”

例题：输入一个正整数n表示有n个节点的树，根节点为1号节点，然后输入n个正整数表示点权，请输出n个数，以每个点为根的子树元素种类数。

只用改写get_ans中的统计方法，以及del中每次初始化的方式即可。

统计方法

void get_data(int x,int op)
{
    for(int i=L[x];i<=R[x];++i)
    {
        if(Index[i]==skp)
        {
            i=R[Index[i]];
            continue;
        }
        cnt[col[Index[i]]]+=op;
        if(cnt[col[Index[i]]]==1)++nowans;
        if(cnt[col[Index[i]]]==0)--nowans;
    }
}

del

if(del)
{
    skp=0;
    get_data(x,-1);
}

注意del这个东西，虽然我们要的效果是将cnt数组和nowans清零，但是实际上我们不能使用memset，否则复杂度会退化为 $O(n^2)$ 。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n;
int g[MAXN],tot,dfn,u,v;
int sz[MAXN],deep[MAXN],fa[MAXN],son[MAXN],L[MAXN],R[MAXN],Index[MAXN],skp,col[MAXN],nowans,ans[MAXN],cnt[MAXN];
struct edges
{
    int to,next;
}e[2*MAXN];
void add_edge(int from,int to)
{
    e[++tot].to=to;
    e[tot].next=g[from];
    g[from]=tot;
    return;
}
void dfs(int x,int dep,int father)
{
    sz[x]=1;
    deep[x]=dep;
    fa[x]=father;
    son[x]=0;
    L[x]=++dfn;
    Index[dfn]=x;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs(e[i].to,dep+1,x);
            sz[x]+=sz[e[i].to];
            if(!son[x]||sz[son[x]]<sz[e[i].to])son[x]=e[i].to;
        }
    }
    R[x]=dfn;
    return;
}
void get_data(int x,int op)
{
    for(int i=L[x];i<=R[x];++i)
    {
        if(Index[i]==skp)
        {
            i=R[Index[i]];
            continue;
        }
        cnt[col[Index[i]]]+=op;
        if(cnt[col[Index[i]]]==1)++nowans;
        if(cnt[col[Index[i]]]==0)--nowans;
    }
}

void dsu(int x,bool del)
{
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to==fa[x]||e[i].to==son[x])continue;
        dsu(e[i].to,true);
    }
    ///skip the heavy son
    if(son[x])
    {
        dsu(son[x],false);
        skp=son[x];
    }
    ///get data from light son and itself
    get_data(x,1);
    ///solve problem with subtree x
    ans[x]=nowans;
    ///if delete clear all
    if(del)
    {
        skp=0;
        get_data(x,-1);
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&col[i]);
    }
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs(1,1,-1);
    dsu(1,0);
    for(int i=1;i<=n;++i)
    {
        printf("%d%c",ans[i],i==n?'\n':' ');
    }
    return 0;
}

dsu on tree与启发式合并

最后解答一下为什么dsu on tree是树上的启发式合并。

启发式合并用于解决这个问题，假设有某种数据结构，支持O(1)的 pop与insert操作，但是没有合并的操作，然后现在让你写一个合并的函数合并这若干个数据结构，如何实现均摊log的代价？

那这个大家都知道是采取“小并大”的策略，也就是对两个数据结构中size较小的那个把所有元素全部pop出来insert到大的当中。这样子操作每次都至少会使得较小数据结构的尺寸翻倍，由于每次暴力合并的复杂度等于较小数据结构的尺寸，那么每个数据结构作为较小的一堆至多合并 $log_2n$ 次（当它作为较大数据结构的一堆参与合并时是不影响复杂度的）。也就是每个元素至多被pop和insert $log_2n$ 次，所以总复杂度为 $nlog_2n$ 。

那其实dsu on tree中有一步也是这样考虑的。

就是在于当出现多个子树进行合并的时候，我们选择最后dfs统计子树x的信息，然后保留这个信息再dfs(rt)

这个过程，就相当于把x,y,z三个子树视为某种数据结构，保留子树x的信息，暴力遍历子树y与子树z的子树信息，往x这个数据结构里面并

这里的某种数据结构，就是树结构本身，从本质上来讲，dsu on tree就是树上的启发式合并算法。

那现在我们利用启发式合并的体系，再次证明dsu on tree的时间复杂度。

在每一层中出现若干个子树，然后对于每一层，合并他们的时间复杂度为 $\sum{size[lch]}$ ,也就是轻儿子的尺寸之和。

那么同样的，每向上一层，轻儿子的尺寸大小至少翻倍一次，那么每个节点至多参与合并 $log_2n$ （当它作为重儿子参与合并时是不影响复杂度的）。

所以总复杂度为 $nlog_2n$ ，从启发式合并的角度再次证明了其时间复杂度。

与深度有关的静态查询类问题

见长链剖分：https://blog.nowcoder.net/n/5eaebd22f5f846838c637bc337cc1ee9