树上启发式合并
title: 树上启发式合并
categories:
- ICPC
tags:
- null
abbrlink: 3a024d41
date: 2023-04-15 00:00:00
树上启发式合并(常常也叫DSU On Tree,但其实和DSU并没有特别大关系),是一种解决某些树上离线问题的算法,尤其常被用于解决“对每个节点,询问关于其子树的某些信息”这样的问题。
- 假设我们要对树上的每个节点p求ans[p] ,且这个ans[p] 可以通过合并p的子节点的某些信息得知,一般来说我们可以用树形DP解决。但如果“子节点的某些信息”的规模较大,简单的树形DP在时间和空间上都可能爆炸。所以我们不能存储每个节点的信息,而是要实现某种资源复用。
- 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。
- 每个结点都有一个颜色,颜色是以编号表示的, $i$ 号结点的颜色编号为 $c_i$。
- 如果一种颜色在以 $x$ 为根的子树内出现次数最多,称其在以 $x$ 为根的子树中占主导地位。显然,同一子树中可能有多种颜色占主导地位。
- 你的任务是对于每一个 $i\in[1,n]$,求出以 $i$ 为根的子树中,占主导地位的颜色的编号和。
- $n\le 10^5,c_i\le n$
时间复杂度O(nlogn)
int read(){
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
const int N=1e5+10;
// col[x]:节点的颜色编号, son[x]:重儿子,
// cnt[i]:颜色编号i的数量
int n,col[N],siz[N],son[N],cnt[N],mx;
LL sum,ans[N];
vector<int> e[N];
void dfs1(int x,int fa){ //重链剖分
siz[x]=1;
for(int y : e[x]){
if(y==fa) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[y]>siz[son[x]]) son[x]=y;
}
}
void add(int x,int fa,int son){
cnt[col[x]]++;
if(cnt[col[x]]>mx) mx=cnt[col[x]],sum=col[x];
else if(cnt[col[x]]==mx) sum+=col[x];
for(int y : e[x]) //重子树除外
if(y!=fa && y!=son) add(y,x,son);
}
void sub(int x,int fa){
cnt[col[x]]--;
for(int y : e[x])
if(y!=fa) sub(y,x);
}
void dfs2(int x, int fa, int opt){
for(int y : e[x]) //先搜轻儿子
if(y!=fa && y!=son[x]) dfs2(y,x,0);
if(son[x]) dfs2(son[x],x,1); //后搜重儿子
add(x,fa,son[x]); //累加x和轻子树贡献
ans[x]=sum; //存储答案
if(!opt)sub(x,fa),sum=mx=0; //减掉轻子树贡献
}
int main(){
n=read();
for(int i=1; i<=n; i++) col[i]=read();
for(int i=1; i<=n-1; i++){
int x=read(),y=read();
e[x].push_back(y); e[y].push_back(x);
}
dfs1(1,0);
dfs2(1,0,0);
for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!