专栏文章

【Trick】dsu on tree

LLinkyChristian
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@ming4zyu
此快照首次捕获于
2025/12/02 01:52
3 个月前
此快照最后确认于
2025/12/02 01:52
3 个月前
查看原文
对一颗树上的信息统计，若能做到O(1)的加入数据和O(1)的删除数据，则可以使用dsu on tree
核心要点是树链，然后用一个数组统计，对于每个点每次先遍历所有轻儿子，每遍历一个轻儿子之后将该儿子子树数据删除，最后遍历重儿子，重儿子遍历出来后数据不删除，加上所有轻儿子子树的数据再加上该点本身的数据作为该点的数据。
其复杂度很好证明，每个点除开第一次被统计，只会额外在祖先链上的每条轻边被删除一次再被统计一次，而祖先链上的轻边不超过log条，所以复杂度为 O(nlogn)O(nlogn)
CF600E Lomsat gelral
CPP
#include<bits/stdc++.h>
#define N 100010
#define pb push_back
#define int long long
using namespace std;
int n,a[N],buc[N],siz[N],son[N],mx,ans[N],mxs;
vector<int> to[N];
void dfs0(int now,int fa) {
	siz[now]=1,son[now]=0;
	for(int v:to[now]) if(v!=fa) {
		dfs0(v,now),siz[now]+=siz[v];
		if(siz[v]>siz[son[now]]) son[now]=v;
	}
}
vector<int> id;
void add(int x) {buc[x]++; if(buc[x]==mx) mxs+=x; if(buc[x]>mx) mx=buc[x],mxs=x;}
void dfs2(int now,int fa) {
	add(a[now]),id.pb(now);
	for(int v:to[now]) if(v!=fa) dfs2(v,now);
}c
void dfs1(int now,int fa) {
	for(int v:to[now]) if(v!=fa&&v!=son[now]) {
		dfs1(v,now);
		for(int x:id) buc[a[x]]=0;mx=mxs=0;id.clear();
	}  
	if(son[now]) dfs1(son[now],now);
	add(a[now]),id.pb(now);
	for(int v:to[now]) if(v!=fa&&v!=son[now]) dfs2(v,now);
	ans[now]=mxs;
}
main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<n; i++) {
		int u,v;cin>>u>>v;
		to[u].pb(v),to[v].pb(u);
	}
	dfs0(1,0),dfs1(1,0);
	for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...