POJ 3107 - Godfather tree DP..vector should be used with caution..._PHP tutorial

The submission timed out... I really don't think there is much to optimize... The most I can do is change it back to the bottom-up BFS... but it's very troublesome and I have to remember a lot of things... I only found out after reading the discussion that it's mainly because of the vector... Change it to a handwritten linked list. .500MS passed,,,

Select any point as the root of the tree... Count the number of subtree elements at each point. For points that are not root... Subtract the number N of all points N from the number of elements of the current subtree num .as another child of the point...

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;
}

http://www.bkjia.com/PHPjc/477206.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/477206.htmlTechArticleSubmission timeout... I really don’t think there is much to optimize... At most, change it back to bottom-up BFS... But it’s so troublesome to remember a lot of things. After reading the discussion, I found out that the main reason is vector.. Changed to handwritten linked list.. 500M...