社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...