提交超时..实在觉得没什么好优化的...最多改回至底而上的BFS..但好麻烦,记一堆东西..看discuss才知道主要是vector的原因..改成手写链表..500MS过,,,
选择任意一个点做树的树的root...统计每个点的子树元素个数情况..对于不是root的点..将所有点数N减去当前子树的元素个数num.作为该点的另一个孩子...
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include<ctime>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 50005
using namespace std;
struct node
{
int x,y,next;
}line[MAXN*2];
int n,AnsNum,AnsData,ans[MAXN],_next[MAXN];
bool used[MAXN];
void addline(int x,int y,int m)
{
line[m].next=_next[x],_next[x]=m;
line[m].x=x,line[m].y=y;
return;
}
int dfs(int x)
{
int MaxSub=0,num=0,t,k;
k=_next[x];
while (k)
{
if (!used[line[k].y])
{
used[line[k].y]=true;
t=dfs(line[k].y);
MaxSub=max(t,MaxSub);
num+=t;
used[line[k].y]=false;
}
k=line[k].next;
}
MaxSub=max(MaxSub,n-(num+1));
if (MaxSub==AnsData) ans[++AnsNum]=x;
else
if (MaxSub<AnsData)
{
AnsData=MaxSub;
AnsNum=0,ans[++AnsNum]=x;
}
return num+1;
}
int main()
{
int i,num;
while (~scanf("%d",&n))
{
memset(_next,0,sizeof(_next));
for (i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addline(x,y,i*2-1);
addline(y,x,i*2);
}
memset(used,false,sizeof(used));
AnsData=oo; used[1]=true;
dfs(1);
sort(ans+1,ans+1+AnsNum);
printf("%d",ans[1]);
for (i=2;i<=AnsNum;i++) printf(" %d",ans[i]);
printf("\n");
}
return 0;
}
