树上启发式合并

引入

启发式算法是什么呢？

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

给个例子？

最常见的就是并查集的按秩合并了，有带按秩合并的并查集中，合并的代码是这样的：

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];
}

在这里，对于两个大小不一样的集合，我们将大小小的并到大的，而不是大的连接小的。

为什么呢？这个集合的大小可以认为是集合的高度（在正常情况下），而我们将集合高度小的并到高度大的显然有助于我们找到父亲

让高度小的树成为高度较大的树的子树，这个优化可以称为启发式合并算法。

算法内容

虽然说是dsu on tree ，但是某个毒瘤@noip 说这个是静态链分治，所以我同时保留两种说法

以下是原话

说实话"dsu on tree"是个极其有问题的民科叫法吧。。（没有怼人的意思。。）

这东西几十年前就有了啊，那个人自己YY了个链分治就瞎起名字。。

树上启发式合并（dsu on tree）对于某些树上离线问题可以速度大于等于大部分算法且更易于理解和实现的算法。

考虑下面的问题：

给出一棵树，每个节点有颜色，询问一些子树的颜色数量（颜色可重复）。

提供一个模板题树上数颜色，数据纯随机，非常弱

对于这种问题解决方式大多是运用大量的数据结构（树套树等），如果可以离线，询问的量巨大，是不是有更简单的方法？

树上莫队!

不行，莫队带根号，我要log

既然支持离线，考虑预处理后O(1)输出答案。

直接暴力预处理的时间复杂度为O(n^2)，即对每一个子节点进行一次遍历，每次遍历的复杂度显然与n同阶，有n个节点，故复杂度为O(n^2)

可以发现，每个节点的答案是其子树的叠加，考虑利用这个性质处理问题

我们可以先预处理出每个节点子树的size和它的重儿子，重儿子同树链剖分一样，是拥有节点最多子树的儿子，这个过程显然可以O(n)完成

我们用check[i]表示颜色i有没有出现过，ans[i]表示他的颜色个数

遍历一个节点，我们按以下的步骤进行遍历：

• 先遍历其非重儿子，获取它的ans，但不保留遍历后它的check

• 遍历它的重儿子，保留它的check

• 再次遍历其非重儿子及其父亲，用重儿子的check对遍历到的节点进行计算，获取整棵子树的ans

上图是一个例子

这样，对于一个节点，我们遍历了一次重子树，两次非重子树，显然是最划算的。

经过这个过程，我们获得了这个节点的子树的所有ans

为什么不合并第一步和第三步呢？因为check数组不能重复使用，否则空间会太大，需要在O(n)的空间内完成。

显然若一个节点u被遍历了x次，则其重儿子会被遍历x次，轻儿子（如果有的话）会被遍历x*2次。

注意除了重儿子，每次遍历完check要清零。

复杂度

（对于不关心复杂度证明的，可以跳过不看）

我们像树链剖分一样定义重边和轻边（连向重儿子的为重边，其余为轻边）关于重儿子和重边的定义，可以见下图，对于一棵有n个节点的树：

根节点到树上任意节点的轻边数不超过logn条。我们设根到该节点有x条轻边该节点的子树大小为y，显然轻边连接的子节点的子树大小小于父亲的一半（若大于一半就不是轻边了），则y<n/2^x，显然n>2^x,所以x<logn。

又因为如果一个节点是其父亲的重儿子，则他的子树必定在他的兄弟之中最多，所以任意节点到根的路径上所有重边连接的父节点在计算答案是必定不会遍历到这个节点，所以一个节点的被遍历的次数等于他到根节点路径上的轻边树+1（之所以要+1是因为他本身要被遍历到），所以一个节点的被遍历次数=logn+1,总时间复杂度则为O(n(logn+1))=O(nlogn)输出答案花费O(m).

图中标红的即为重边，重边连向的子节点为重儿子

大致代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int maxn=100010;
struct node{
    int to,nxt;
}t[maxn];int head[maxn],tot=0;
inline void addedge(int x,int y){
    t[++tot].to=y;
    t[tot].nxt=head[x];
    head[x]=tot;
}

int c[maxn],size[maxn],son[maxn],cnt[maxn],ans[maxn];
//  color   size       重儿子    计数器  

void dfs1(int x,int fa){
    size[x]=1;
    for(int i=head[x];i;i=t[i].nxt){
        int to=t[i].to;
        if(to!=fa){
            dfs1(to,x);
            size[x]+=size[to];
            if(size[to]>size[son[x]])
                son[x]=to;
        }
    }
}
//                    重儿子    保留答案
int dfs2(int u,int fa,int isson,int keep){
    if(keep){
        for(int i=head[u];i;i=t[i].nxt){
            int to=t[i].to;
            if(to!=fa&&to!=son[u]){
                dfs2(to,u,0,1);
            }
        }
    }
    int tmp=0;
    if(!keep&&son[u])tmp+=dfs2(son[u],u,1,0);
    else if(son[u]) tmp+=dfs2(son[u],u,1,1);
    for(int i=head[u];i;i=t[i].nxt){
        int v=t[i].to;
        if(v!=fa&&v!=son[u]){
            tmp+=dfs2(v,u,0,0);
        }
    }
    if(!cnt[c[u]]){
        tmp++;
    }
    cnt[c[u]]++;
    if(keep)ans[u]=tmp;
    if(keep&&!isson) memset(cnt,0,sizeof(cnt));
    return tmp;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
    }
    dfs1(1,0);
    dfs2(1,0,1,1);
    int m;
    scanf("%d",&m);
    while(m--){
        int x;
        cin>>x;
        cout<<ans[x]<<endl;
    }
    return 0;
}

运用

1.某些出题人设置的正解是树上启发式合并的题

如CF741D,给一棵树，每个节点的权值是'a'到'v'的字母，每次询问要求在一个子树找一条路径，使该路径包含的字符排序后成为回文串。

因为是排列后成为回文串，所以一个字符出现了两次相当于没出现，也就是说，这条路径满足最多有一个字符出现奇数次

正常做法是对每一个节点dfs，每到一个节点就强行枚举所有字母找到和他异或后结果为1的个数<1的路径，再去最长值，这样O(n^2logn)的，可以用dsu on tree优化到O(nlog^2n).关于具体做法，可以参考下面的扩展阅读

2.可以用启发式合并乱搞水分的题

可以水一些树套树的部分分（没有修改操作）,还可以把树上莫队的O(n\sqrt{m})吊着打，而且也比树链剖分好写，且常数小

练习题

CF600E Lomsat gelral

题意翻译：树的节点有颜色，一种颜色占领了一个子树，当且仅当没有其他颜色在这个子树中出现得比它多。求占领每个子树的所有颜色之和。

UOJ284 快乐游戏鸡

参考资料/扩展阅读

CF741D作者介绍的dsu on tree

这位作者的题解