求助各位dalao正误原因
查看原帖
求助各位dalao正误原因
676591
Schrochanshun楼主2023/10/30 20:52

为何正确写法仅仅比错误写法改了一小部分地方就过了,主要差别在代码中已经标记出来,求助各位大佬

//错误做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int n,idx,h[N],e[N],ne[N];
int l[N],r[N],node[N],tr[N],hson[N],dfn;
ll col[N],ans[N],cnt[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int p)
{
	l[u]=++dfn;
	node[dfn]=u;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p)
		{
			dfs(j,u);
			tr[u]+=tr[j];
			if(tr[j]>tr[hson[u]])	hson[u]=j;
		}
	}
	r[u]=dfn;
}
void dfs1(int u,int p,int tag)
{
	ll mx=0,sum=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p&&j!=hson[u])	dfs1(j,u,0);
	}
  //主要差别
	if(hson[u])	
	{
		dfs1(hson[u],u,1);
		for(int j=l[hson[u]];j<=r[hson[u]];j++)
		{
			ll a=col[node[j]];
			if(cnt[a]>mx)	
			{
				sum=a;
				mx=cnt[a];
			}
			else if(cnt[a]==mx)	sum+=a;
		}
	}
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p&&j!=hson[u])
		{
			for(int k=l[j];k<=r[j];k++)
			{
				ll a=col[node[k]];
				cnt[a]++;
				if(cnt[a]>mx)	
				{
					mx=cnt[a];
					sum=a;
				}
				else if(cnt[a]==mx)	sum+=a;
			}
		}
	}
	cnt[col[u]]++;
	if(cnt[col[u]]>mx)	mx=cnt[col[u]],sum=col[u];
	else if(cnt[col[u]]==mx)	sum+=col[u];
	ans[u]=sum;
	if(!tag)
	{
		for(int i=l[u];i<=r[u];i++)
		{
			ll a=col[node[i]];
			cnt[a]--;
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	
	{
		int a;
		scanf("%d",&a);
		col[i]=a;
		tr[i]=1;
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	dfs1(1,0,1);
	for(int i=1;i<=n;i++)	printf("%lld ",ans[i]);
	return 0;
}
//正确做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200010;
int n,idx,h[N],e[N],ne[N];
int l[N],r[N],node[N],tr[N],hson[N],cnt[N],dfn;
ll mx,sum,col[N],ans[N];
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int p)
{
	l[u]=++dfn;
	node[dfn]=u;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p)
		{
			dfs(j,u);
			tr[u]+=tr[j];
			if(tr[j]>tr[hson[u]])	hson[u]=j;
		}
	}
	r[u]=dfn;
}
void dfs1(int u,int p,int tag)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p&&j!=hson[u])	dfs1(j,u,0);
	}
  //主要差别点
	if(hson[u])	dfs1(hson[u],u,1);
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=p&&j!=hson[u])
		{
			for(int k=l[j];k<=r[j];k++)
			{
				ll a=col[node[k]];
				cnt[a]++;
				if(cnt[a]>mx)	
				{
					mx=cnt[a];
					sum=a;
				}
				else if(cnt[a]==mx)	sum+=a;
			}
		}
	}
	cnt[col[u]]++;
	if(cnt[col[u]]>mx)	mx=cnt[col[u]],sum=col[u];
	else if(cnt[col[u]]==mx)	sum+=col[u];
	ans[u]=sum;
	if(!tag)
	{
		for(int i=l[u];i<=r[u];i++)
		{
			ll a=col[node[i]];
			cnt[a]--;
			mx=sum=0;
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	
	{
		int a;
		scanf("%d",&a);
		col[i]=a;
		tr[i]=1;
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	dfs1(1,0,0);
	for(int i=1;i<=n;i++)	printf("%lld ",ans[i]);
	return 0;
}
2023/10/30 20:52
加载中...