树上启发式合并(dsu on tree)学习笔记

发布于 2021-08-09  96 次阅读


参考:p_z_y 的博客,YellowBean 的代码启示。

尽量写短点。

dsu on tree

模板题:CF600E Lomsat gelral

题意:

  • 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树
  • 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。
  • 如果一种颜色在以 $x$ 为根的子树内出现次数最多,称其在以 $x$ 为根的子树中占主导地位。显然,同一子树中可能有多种颜色占主导地位。
  • 你的任务是对于每一个 $i\in[1,n]$,求出以 $i$ 为根的子树中,占主导地位的颜色的编号和。
  • $n\le 10^5,c_i\le n$。

首先我们考虑 $n^2$​ 的做法,对于每一个点遍历整棵子树暴力统计答案即可。

好了,dsu on tree 完成一半了。

我们发现子树和父亲之间有很多结点是重复的,考虑把他利用上。我们无法同时保存两个儿子所在子树的结果,因为我们在处理另一个儿子的答案时,已有的信息会对其产生干扰。我们可以做的仅仅是对于最后遍历的那个儿子,我们保留其信息,而对于之前遍历的儿子,只能清除。

猜测保留重儿子的信息是最优的,因为这样不同统计的结点最多。这就是 dsu on tree了。

具体的实现(引用自 p_z_y 的博客):

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

即:先处理完轻儿子的答案并消除贡献,再去处理重儿子的答案并保留贡献,再暴力统计轻儿子的贡献从而得出当前结点的答案即可。

代码部分

建树后,先处理出轻儿子。

inline void dfs1(int u,int f){
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}

接着直接 dsu on tree,详见注释。

inline void Dfs(int u,int f,int p){//暴力统计贡献
    t[c[u]]++;
    if(t[c[u]]>mx){
        mx=t[c[u]];
        sum=c[u];
    }
    else if(t[c[u]]==mx) sum+=c[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f||v==p) continue;
        Dfs(v,u,p);//重儿子答案统计好了,不用跑也不能跑
    }
}
inline void clean(int u,int f){//消除贡献
    t[c[u]]--;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f) continue;
        clean(v,u);
    }
}
inline void dfs(int u,int f){//dsu on tree 主函数
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f||v==son[u]) continue;
        dfs(v,u);clean(v,u);sum=mx=0;//处理轻儿子并消除贡献
    }
    if(son[u]) dfs(son[u],u);//处理重儿子,不消除贡献
    Dfs(u,f,son[u]);ans[u]=sum;//暴力跑完轻儿子后统计答案
}

复杂度证明

由于每一个点到根最多只有 $\log n$ 条轻边,而我们发现一个点到根每有一条轻边,其就会被暴力统计贡献一次,因此一个点最多被暴力统计 $\log n$ 次,故时间复杂度为 $O(n\log n)$。

几道例题

CF570D Tree Requests

题意:

  • 给定一个以 $1$​ 为根的 $n$​ 个结点的树,每个点上有一个字母(a-z),每个点的深度定义为该节点到 $1$​ 号结点路径上的点数。每次询问 $a, b$​ 查询以 $a$​ 为根的子树内深度为 $b$​ 的结点上的字母重新排列之后是否能构成回文串。

发现能构成回文串当且仅当奇数个数的字母种数不大于 $1$。记 $t_{dep,0\sim25}$ 为深度为 $dep$ 的点中各个字母出现的次数,用 dsu on tree 处理再每次遍历 $26$ 个字母统计答案即可。

CF246E Blood Cousins Return

题意:

  • 给定一片森林,每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为深度是该节点深度加 $K$​ 的节点。

跟上题差不多,用 map 存每层每个名字出现了多少次,再给每一次搞一个 set,新名字丢进去,名字没了删掉,然后统计答案时直接调出其中的 size 即可。

CF208E Blood Cousins

题意:

  • 给你一片森林,每次询问一个点与多少个点拥有共同的 $K$​ 级祖先。

先倍增跑出询问点的 $K$ 级祖先是谁,再把询问打在这个 $K$​ 级祖先上,就变成了统计子树内某个深度的点有多少个,容易用 dsu on tree 解决。

完整代码(CF600E)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,c[N],mx;
ll sum,ans[N];
struct node{
    int to,nxt;
}e[N<<1];
int cnt,head[N],t[N];
inline void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int son[N],siz[N];
inline void dfs1(int u,int f){
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
inline void Dfs(int u,int f,int p){
    t[c[u]]++;
    if(t[c[u]]>mx){
        mx=t[c[u]];
        sum=c[u];
    }
    else if(t[c[u]]==mx) sum+=c[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f||v==p) continue;
        Dfs(v,u,p);
    }
}
inline void clean(int u,int f){
    t[c[u]]--;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==f) continue;
        clean(v,u);
    }
}
inline void dfs(int u,int f){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f||v==son[u]) continue;
        dfs(v,u);clean(v,u);sum=mx=0;
    }
    if(son[u]) dfs(son[u],u);
    Dfs(u,f,son[u]);ans[u]=sum;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs1(1,1);
    dfs(1,1);
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣