POJ 1655 BalanceAct 3107 Godfather (树的重心)(树形DP)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn=20010;
 8 const int maxx=1<<30;
 9 int t,n;
10 int f[maxn]={};
11 int vis[maxn]={};
12 struct nod{
13     int y;
14     int next;
15 }e[2*maxn]={};
16 int head[maxn]={},tot=0;
17 int ans,size=0;
18 void init(int x,int y){
19     e[++tot].y=y;
20     e[tot].next=head[x];
21     head[x]=tot;
22 }
23 void dfs(int x){
24     int y;
25     vis[x]=1;
26     f[x]=0;
27     int tmp=0;
28     for(int i=head[x];i;i=e[i].next){
29         y=e[i].y;
30         if(!vis[y]){
31             dfs(y);
32             f[x]+=f[y]+1;
33             tmp=max(tmp,f[y]+1);
34         }
35     }tmp=max(tmp,n-f[x]-1);
36     if(tmp<size||(tmp==size&&x<ans)){
37         size=tmp;
38         ans=x;
39     }
40 }
41 void yu(){
42     size=maxx;
43     ans=maxx;
44     tot=0;
45     memset(f,0,sizeof(f));
46     memset(vis,0,sizeof(vis));
47     memset(head,0,sizeof(head));
48     memset(e,0,sizeof(e));
49 }
50 int main(){
51     scanf("%d",&t);
52     while(t-->0){
53         yu();
54         scanf("%d",&n);
55         int x,y;
56         for(int i=1;i<n;i++){
57             scanf("%d%d",&x,&y);
58             init(x,y);
59             init(y,x);
60         }
61         dfs(1);
62         printf("%d %d\n",ans,size);
63     }
64     return 0;
65 }