学步园

此题和poj1655算法一样，只是数据量较大，我开始动态分配空间建立邻接表超时了，改为了静态的610ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 50005;
struct node
{
     int x,y,next;
};
node edge[N*2];
int num[N],dp[N],head[N],vis[N],n;
int dfs1(int u)//求以u为根的树中节点的个数
{
     vis[u]=1;
     num[u]=1;
     int v=head[u];
     while(v)
     {
          if(!vis[edge[v].y])
          {
               num[u]+=dfs1(edge[v].y);
          }
          v=edge[v].next;
     }
     vis[u]=0;
     return num[u];
}
void dfs2(int u)
{
     vis[u]=1;
     dp[u]=0;
     int v=head[u];
     while(v)
     {
          if(!vis[edge[v].y])
          {
               dp[u]=max(dp[u],num[edge[v].y]);
               dfs2(edge[v].y);
          }
          v=edge[v].next;
     }
     dp[u]=max(dp[u],n-num[u]);
}
int main()
{
     while(scanf("%d",&n)!=EOF)
     {
          memset(head,0,sizeof(head));
          int x,y;
          for(int i=1;i<n;i++)//利用静态链表建图
          {
               scanf("%d %d",&x,&y);
               edge[i*2-1].x=x;
               edge[i*2-1].y=y;
               edge[i*2-1].next=head[x];
               head[x]=i*2-1;
               edge[i*2].x=y;
               edge[i*2].y=x;
               edge[i*2].next=head[y];
               head[y]=i*2;
          }
          memset(vis,0,sizeof(vis));
          dfs1(1);
          dfs2(1);
          int ansi=1;
          for(int i=2;i<=n;i++)
          {
               if(dp[ansi]>dp[i])
               {
                    ansi=i;
               }
          }
          int cnt=0;
          for(int i=1;i<=n;i++)
          {
               if(dp[i]==dp[ansi])
               {
                    if(cnt)
                         printf(" ");
                    cnt++;
                    printf("%d",i);
               }
          }
          printf("\n");
     }
     return 0;
}