dsu on tee相关题目练习（DFS)

1.U41492 树上数颜色


dsu on tree 裸题，具体看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int>v[N];
int col[N],hev[N],sz[N],cnt[N],mx,son,n;
ll sum,ans[N];
void dfs1(int u,int fa){
	sz[u]=1;
	for(int i=0;i<v[u].size();i++)
	{
		int to=v[u][i];
		if(to!=fa)
		{
			dfs1(to,u);
			sz[u]+=sz[to];
			if(sz[to]>sz[hev[u]]) hev[u]=to;//更新轻重链部分 
		}
	}
}
void add(int u,int fa,int val){
	 //printf("u=%d,fa=%d,val=%d\n",u,fa,val); 
	 cnt[col[u]]+=val;
	 if(val==1&&cnt[col[u]]==1) sum++; ///根据题目要求修改。 
	 else if(val==-1&&cnt[col[u]]==0) sum--; 
	 for(int i=0;i<v[u].size();i++){
	 	  int to=v[u][i];
	 	  if(to!=fa&&to!=son) //统计所有轻儿子贡献。 
	 	  	add(to,u,val);
	 }
}
void dfs2(int u,int fa,int opt){ //opt表示十分消除贡献 0表示消除，1表示不消除 
	 //printf("u=%d,fa=%d,opt%d\n",u,fa,opt); 
	 for(int i=0;i<v[u].size();i++)
	 {
	 	 int to=v[u][i];
	 	 if(to!=fa&&to!=hev[u])
	 	 		dfs2(to,u,0);//搜索所有轻边，递归完成后消除对该点的影响 
	 }
	 if(hev[u]) dfs2(hev[u],u,1),son=hev[u];//搜索重边，且不消除影响。 
	 //最后搜索重边不删除影响 叶子结点没有轻儿子，相当于自己就是轻儿子。下面的add(u,fa,1)就是加上自己 
	 add(u,fa,1),son=0;//暴力统计所有轻儿子的贡献 
	 ans[u]=sum;
	 if(!opt) add(u,fa,-1),sum=mx=0;//如果不是重儿子就消除影响，如果是重儿子（最后搜索）就保存影响。最后直接加上轻儿子的贡献就是总贡献 
} 
int main(){
	cin>>n;
	for(int i=1,a,b;i<=n-1;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=n;i++) cin>>col[i];
	dfs1(1,0);
	dfs2(1,0,0);
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}

2.E. Lomsat gelral

CF600E模板题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int>v[N];
int col[N],hev[N],sz[N],cnt[N],mx,son,n;
ll sum,ans[N];
void dfs1(int u,int fa){
	sz[u]=1;
	for(int i=0;i<v[u].size();i++)
	{
		int to=v[u][i];
		if(to!=fa)
		{
			dfs1(to,u);
			sz[u]+=sz[to];
			if(sz[to]>sz[hev[u]]) hev[u]=to;//更新轻重链部分 
		}
	}
}
void add(int u,int fa,int val){
	 //printf("u=%d,fa=%d,val=%d\n",u,fa,val); 
	 cnt[col[u]]+=val;  ///这一块根据题目具体要求修改 
	 if(cnt[col[u]]>mx) mx=cnt[col[u]],sum=col[u];
	 else if(cnt[col[u]]==mx) sum+=(ll)col[u];
	 for(int i=0;i<v[u].size();i++){
	 	  int to=v[u][i];
	 	  if(to!=fa&&to!=son) //统计所有轻儿子贡献。 
	 	  	add(to,u,val);
	 }
}
void dfs2(int u,int fa,int opt){ //opt表示十分消除贡献 0表示消除，1表示不消除 
	 printf("u=%d,fa=%d,opt%d\n",u,fa,opt); 
	 for(int i=0;i<v[u].size();i++)  ////搜索n个结点复杂度 O(n) 任意点到根的路径最多有logn个轻边 重边不用删除 所以时间复杂度为O(nlogn) 
	 {
	 	 int to=v[u][i];
	 	 if(to!=fa&&to!=hev[u])
	 	 		dfs2(to,u,0);//搜索所有轻边，递归完成后消除对该点的影响 
	 }
	 if(hev[u]) dfs2(hev[u],u,1),son=hev[u];//搜索重边，且不消除影响。 
	 //最后搜索重边不删除影响 叶子结点没有轻儿子，相当于自己就是轻儿子。下面的add(u,fa,1)就是加上自己 
	 add(u,fa,1),son=0;//暴力统计所有轻儿子的贡献 
	 ans[u]=sum;
	 if(!opt) add(u,fa,-1),sum=mx=0;//如果不是重儿子就消除影响，如果是重儿子（最后搜索）就保存影响。最后直接加上轻儿子的贡献就是总贡献 
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>col[i];
	for(int i=1,a,b;i<=n-1;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs1(1,0);
	dfs2(1,0,0);
	for(int i=1;i<=n;i++) printf(i==n?"%lld\n":"%lld ",ans[i]);
	return 0;
}