poj 2378 Tree Cutting

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<queue>
 6 #include<vector>
 7 #include<algorithm>
 8 using namespace std;
 9 
10 vector<int>Q[10002];
11 int num[10002];
12 int dp[10002][2];
13 bool use[10002];
14 int Queue[10002],len;
15 //dp[i][0] ×ó?úμ?μ?×?′óêyá?
16 //dp[i][1] í3?? ×ó?úμ??°×?éí μ?×ü??êy
17 
18 void add(int x,int y)
19 {
20     Q[x].push_back(y);
21     num[x]++;
22 }
23 int Max(int x,int y)
24 {
25     return x>y? x:y;
26 }
27 void dfs(int k)
28 {
29     int i,t,cur=0;
30     use[k]=true;
31     dp[k][1]=1;
32     for(i=0;i<num[k];i++)
33     {
34         t=Q[k][i];
35         if(use[t]==true)continue;
36         dfs(t);
37         if(cur<dp[t][1])
38             cur=dp[t][1];
39         dp[k][1]=dp[k][1]+dp[t][1];
40     }
41     dp[k][0]=cur;
42 }
43 int main()
44 {
45     int n;
46     int i,x,y,cur;
47     while(scanf("%d",&n)>0)
48     {
49         for(i=0;i<=n;i++)
50         {
51             Q[i].clear();
52             num[i]=0;
53         }
54         memset(dp,0,sizeof(dp));
55         memset(use,false,sizeof(use));
56 
57         for(i=1;i<n;i++)
58         {
59             scanf("%d%d",&x,&y);
60             add(x,y);
61             add(y,x);
62         }
63         dfs(1);
64         for(i=1,len=0;i<=n;i++)
65         {
66             cur=Max(dp[i][0],n-dp[i][1]);
67             if(cur<=n/2)
68             {
69                 Queue[++len]=i;
70             }
71         }
72         if(len==0)printf("NONE\n");
73         else
74         {
75             sort(Queue+1,Queue+1+len);
76             for(i=1;i<=len;i++)
77                 printf("%d\n",Queue[i]);
78         }
79     }
80     return 0;
81 }