| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
物是人非~#include<map>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 55555
#define INF 0x3f3f3f3f
struct node
{
int to,next;
}Edge[N<<1];
int head[N],n,cnt,num[N],ans,Min;
int vec[N],Size;
void add(int w,int v)
{
Edge[cnt].to=v;
Edge[cnt].next=head[w];
head[w]=cnt++;
Edge[cnt].to=w;
Edge[cnt].next=head[v];
head[v]=cnt++;
}
void Tree_DP(int w,int fa)
{
int i,j,k,tot=0,Max=-1;
for(i=head[w];~i;i=Edge[i].next)
{
int v=Edge[i].to;
if(v==fa)continue;
//printf("%d %d \n",w,v);
Tree_DP(v,w);
num[w]+=num[v];
}
}
void dfs(int w,int fa)
{
// printf("w=====%d %d",w,fa);
int i,j,k,tot=0,Max=-1;
for(i=head[w];~i;i=Edge[i].next)
{
int v=Edge[i].to;//printf("w==%d %d \n",w,v);
if(v==fa)continue;
dfs(v,w);
Max=max(Max,num[v]);
tot+=num[v];
}
Max=max(Max,n-1-tot);
if(Max<Min)
{
Min=Max;
Size=0;
vec[Size++]=w;
}
else if(Max==Min)
vec[Size++]=w;
// vec.push_back(w);
}
int main()
{
int m,j,i,k,l;
while(~scanf("%d",&n))
{
Size=0;
memset(head,-1,sizeof(head));
cnt=0;
for(i=1;i<n;i++)
scanf("%d%d",&j,&k),add(j,k),num[i]=1;
num[n]=1;
Min=INF;
Tree_DP(1,0);
dfs(1,0);
sort(vec,vec+Size);
for(i=0;i<Size;i++)
{
printf("%d",vec[i]);
if(i!=Size-1)
printf(" ");
else
printf("\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator