POJ 3107 - Godfather 樹型DP..vector慎用...

 提交超時..實在覺得沒什麼好優化的...最多改回至底而上的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;
}