树形DP poj1655

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 int num;
 8 int head[20010];
 9 int dp[20010];
10 int val[20010];
11 int n;
12 
13 struct edge
14 {
15     int fro,to,next;
16 }e[40100];
17 
18 void addEdge(int _fro,int _to)
19 {
20     num++;
21     e[num].fro=_fro;
22     e[num].to=_to;
23     e[num].next=head[_fro];
24     head[_fro]=num;
25 }
26 
27 void dfs(int x,int from)
28 {
29     if(dp[x]!=0)
30         return;
31     dp[x]=1;
32     for(int i=head[x];i!=-1;i=e[i].next)
33     {
34         int sum=0;
35         int v=e[i].to;
36         dfs(v,e[i].fro);
37         if(v==from)
38             continue;
39         val[e[i].fro]=max(val[e[i].fro],dp[v]);
40         dp[e[i].fro]+=dp[v];
41     }
42     val[x]=max(val[x],n-dp[x]);
43 }
44 
45 int main()
46 {
47     int T;
48     cin>>T;
49     while(T--)
50     {
51         scanf("%d",&n);
52         num=0;
53         memset(head,-1,sizeof(head));
54         memset(dp,0,sizeof(dp));
55         memset(val,0,sizeof(val));
56         int a,b;
57         for(int i=0;i<n-1;i++)
58         {
59             scanf("%d%d",&a,&b);
60             addEdge(a,b);
61             addEdge(b,a);
62         }
63         dfs(1,0);
64         int ans=1<<29;
65         int se;
66         for(int i=1;i<=n;i++)
67         {
68             if(val[i]<ans)
69             {
70                 ans=val[i];
71                 se=i;
72             }
73         }
74         cout<<se<<" "<<ans<<endl;
75     }
76     return 0;
77 }
View Code