dsu on tree（树上启发式合并）学习笔记

最近队友都学了这个算法,我也来凑个热闹学习一下. Dsu on tree:目前我的理解就是一种对树上利用轻重链的性质进行子树统计的一种优化方法 因为一些问题中,需要反复清空子树的一些信息,防止其对隔壁树的兄弟信息统计进行干扰 而对于最后一颗需要进行统计的树,显然它是不用被清空的,而且它的信息在回溯时也能被其父亲使用. 那么,我们选择节点数最多的子树(重儿子)进行信息的保留,而对其他的子树(轻儿子)进行信息的清空. 在诸多dfs中,我们只需记住这一性质就能理解这个算法了,保留当前重儿子信息,清空当前节点轻儿子的信息. 这里重儿子信息的保留是相对于当前节点而言的,并不是说那颗子树不会被清空,当某个重儿子的父亲是一个轻儿子节点时,显然,这个父亲的信息被清空,这个所谓的重儿子信息也会被清空. 所以,轻重儿子信息的节点应当是基于你现在dfs进行的u节点而言的. 学习资料: 资料1 资料2 问题提出:给一个树,树上每个节点有若干个颜色,有q次询问, 每次询问 u , c o l o r u,color u,color.你需要回答以 u u u为子树,包含颜色为 c o l o r color color的树有多少. 方法引入:在一般的dfs上加上轻重儿子的定义,对于重儿子,不清空,轻儿子就清空. 由于轻重链的一些性质,每个轻儿子只会被清空 l o g n logn logn次,所以整个复杂度是 O ( n l o g n ) O(nlogn) O(nlogn) 以下是模仿文章的一个写法:

vector G[maxn];int sz[maxn];
void dfs1(int u,int fa){
	sz[u]=1;
	for(auto v :G[u]){
		if(v!=fa) dfs1(v,u),sz[u]+=sz[v];
	}
}
int cnt[maxn];bool big[maxn];int color[maxn];
void add(int u,int fa,int x){
	cnt[color[u]]+=x;
	for(auto v : G[u]){
		if(v!=fa&&big[v]==false) add(v,u,x);
	}
}
ll ans[maxn];
void dfs(int u,int fa,bool keep){
	int mx = -1,bigchild=-1;
	for(auto v : G[u]){
		if(v!=fa&&sz[v]>mx) mx = sz[v],bigchild=v;
	}
	for(auto v :G[u]){
		if(v!=fa&&v!=bigchild) dfs(v,u,0);
	}
	if(bigchild!=-1) dfs(bigchild,u,1),big[bigchild]=1;
	add(u,fa,1);
	//此时,该点u为根的子树已经统计完毕,应当在这里进行问题的回答
	if(bigchild!=-1) big[bigchild]=0;
	if(keep==0) add(u,fa,-1);//如果u是轻儿子,那么需要清空信息,请注意,信息只能在此清空,当前节点为轻节点时
	//u是重儿子就不需要清空信息,因为是最后一次询问了 
}

例题1,CF600E Lomsat gelral 题意:有一棵 n 个结点的以 1 号结点为根的有根树。 每个结点都有一个颜色 如果一种颜色在以 x 为根的子树内出现次数最多，称其在以 x 为根的子树中占主导地位。显然，同一子树中可能有多种颜色占主导地位。 你的任务是对于每一个 i ∈ [ 1 , n ] i\in[1,n] i∈[1,n]，求出以 i i i为根的子树中，占主导地位的颜色的编号和. 这是例题,显然可以套用上述的模板,要注意的点只有一点.我们说过,重儿子的信息由于是最后才dfs,所以它不用清空,换而言之,重儿子的信息需要被重复利用,所以外部变量res,mx的清空应当在keep==0的条件下清空,保证不会清空到重儿子的res和mx的信息,否则会造成错误. 代码变量名起的不好,全局变量MX,和找重儿子sz的mx冲突了.下回改改 AC代码:

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
vector G[maxn];int sz[maxn];
void dfs1(int u,int fa){
	sz[u]=1;
	for(auto v :G[u]){
		if(v!=fa) dfs1(v,u),sz[u]+=sz[v];
	}
}
int cnt[maxn];bool big[maxn];int color[maxn];
ll res=0,MX = 0;
void add(int u,int fa,int x){
	cnt[color[u]]+=x;
	if(x==1){
		//只在x==1时才能统计答案,
		if(MXmx) mx = sz[v],bigchild=v;
	}
	for(auto v :G[u]){
		if(v!=fa&&v!=bigchild) dfs(v,u,0);
	}
	if(bigchild!=-1) dfs(bigchild,u,1),big[bigchild]=1;
	add(u,fa,1);
	//此时,该点u为根的子树已经统计完毕,应当在这里进行问题的回答
	ans[u] = res;
	if(bigchild!=-1) big[bigchild]=0;
	if(keep==0) add(u,fa,-1),res = MX = 0;//如果u是轻儿子,那么需要清空信息
	//u是重儿子就不需要清空信息,因为是最后一次询问了 
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i>color[i];
	for(int i=1;i>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs(1,0,0);
	for(int i=1;im;
	for(int i=2,x;i>x;G[i].pb(x);G[x].pb(i);
	}
	for(int i=1;i>tmp;
		ch[i] = tmp-'a';
	}
	for(int i=1;i>a>>b;
		q[a].push_back({b,i});
	}
	dfs1(1,0);
	dfs(1,0,0);
	for(int i=1;im;
	for(int i=1;i>color[i];
	}
	for(int i=1;i>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	for(int i=1;i>u>>k;
		q[u].push_back({k,i});
	}
	dfs1(1,0);
	dfs(1,0,0);
	for(int i=1;ia[i];
	}
	for(int i=1,u,v;i>u>>v;G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs(1,0,0);
	coutmx) mx = sz[v],bigchild=v;
	}
	for(auto v :G[u]){
		if(v!=fa&&v!=bigchild) dfs(v,u,0);
	}
	if(bigchild!=-1) dfs(bigchild,u,1),big[bigchild]=1;
	add(u,fa,1);
	//此时,该点u为根的子树已经统计完毕,应当在这里进行问题的回答
	ans[u] = dis - depth[u];
	if(bigchild!=-1) big[bigchild]=0;
	if(keep==0) add(u,fa,-1),dis = 0,num = 0;//如果u是轻儿子,那么需要清空信息,请注意,信息只能在此清空,当前节点为轻节点时
	//u是重儿子就不需要清空信息,因为是最后一次询问了 
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	for(int i=1;i>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs(1,0,0);
	for(int i=1;i