社区讨论

为什么re

学术版参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m57xapay
此快照首次捕获于
2024/12/28 16:31
去年
此快照最后确认于
2024/12/28 20:29
去年
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct node{
	int top=0,chi[10005],fa;
}tree[10005];
int n;
int f[10005],s[10005];
void dp(int x,int root)
{
	f[x]=1;
	if (tree[x].top==0)
		return;
	for(int i=1;i<=tree[x].top;i++)
	{
		int y=tree[x].chi[i];
		if(y!=root)
		{
			dp(y,x);
			s[x]=max(s[x],f[y]);
			f[x]+=f[y];
		}
	}
	s[x]=max(s[x],n-f[x]);
}
int main()
{
// 	freopen("focus.in","r",stdin);
//	freopen("focus.out","w",stdout);
	cin>>n;	
	for(int i=1;i<n;i++)
	{
		int fr,to;
		scanf("%d%d",&fr,&to);
		tree[to].fa=fr;
		tree[fr].chi[++tree[fr].top]=to;
		tree[fr].fa=to;
		tree[to].chi[++tree[to].top]=fr;
	}
	dp(1,0);
	int minn=2e9;
	for(int i=1;i<=n;i++)
		minn=min(minn,s[i]);
	for(int i=1;i<=n;i++)
		if(s[i]==minn)
			cout<<i<<endl;
	return 0;
}
1<=n<=1e4

回复

2 条回复,欢迎继续交流。

正在加载回复...