POJ1655 Balancing Act（树的重心）

树的重心即树上某结点，删除该结点后形成的森林中包含结点最多的树的结点数最少。

一个DFS就OK了。。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define MAXN 222222

 struct Edge{

     int u,v,next;

 }edge[MAXN<<];

 int NE,head[MAXN];

 void addEdge(int u,int v){

     edge[NE].u=u; edge[NE].v=v; edge[NE].next=head[u];

     head[u]=NE++;

 }

 int n,size[MAXN],x,y;

 void dfs(int u,int fa){

     int cnt=,res=;

     for(int i=head[u]; i!=-; i=edge[i].next){

         int v=edge[i].v;

         if(v==fa) continue;

         dfs(v,u);

         cnt+=size[v];

         res=max(res,size[v]);

     }

     size[u]=cnt;

     res=max(res,n-size[u]);

     if(y>res) y=res,x=u;

     else if(y==res && x>u) x=u;

 }

 int main(){

     int t,a,b;

     scanf("%d",&t);

     while(t--){

         NE=;

         memset(head,-,sizeof(head));

         scanf("%d",&n);

         for(int i=; i<n; ++i){

             scanf("%d%d",&a,&b);

             addEdge(a,b); addEdge(b,a);

         }

         y=(<<);

         dfs(,);

         printf("%d %d\n",x,y);

     }

     return ;

 }