0pts,全WA
查看原帖
0pts,全WA
920406
违规用户名920406楼主2024/4/29 21:51
#include <cstdio>
#include <vector>
const int N=5e4+9;
std::vector<int> tree[N];
int n,sum[N],dp[N],x,y,ans=1;
void dfs(int k)
{
	sum[k]=1;
	if(!tree[k].empty())
		for(int i=0;i<tree[k].size();i++)
		{
			dfs(tree[k][i]);
			sum[k]+=sum[tree[k][i]];
		}
}
int DP(int k)
{
	int ans=0;
	for(int i=0;i<tree[k].size();i++)
		ans+=DP(tree[k][i])+sum[tree[k][i]];
	return ans;
}
void dfs2(int k)
{
	for(int i=0;i<tree[k].size();i++)
	{
		int x=tree[k][i];
		dp[x]=dp[k]+n-2*sum[x];
		dfs2(x); 
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		if(x>y)	x^=y,y^=x,x^=y;
		tree[x].push_back(y);
	}
	dfs(1);
	dp[1]=DP(1);
	dfs2(1);
	for(int i=1;i<=n;i++)
		if(dp[i]<dp[ans])
			ans=i;
	printf("%d %d",ans,dp[ans]);
	return 0;
}
//主要方法:先求得在1点开会的距离,在通过dp实现 O(1)转移,即可求出答案
2024/4/29 21:51
加载中...