poj 2378(树形dp)

思路：num[u]表示以u为根的子树的顶点个数（包括），如果去掉u之后u的每棵子树都小于等于n/2，则选择u。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 #define MAXN 11111
 8 #define FILL(a,b) memset(a,b,sizeof(a))
 9 
10 int n,num[MAXN];
11 bool mark[MAXN];
12 vector<vector<int> >g;
13 
14 int dfs(int u,int father)
15 {
16     num[u]=1;
17     bool flag=true;
18     for(int i=0;i<g[u].size();i++){
19         int v=g[u][i];
20         if(v==father)continue;
21         int tmp=dfs(v,u);
22         if(tmp>n/2)flag=false;
23         num[u]+=num[v];
24     }
25     if(flag&&n-num[u]<=n/2)mark[u]=true;
26     return num[u];
27 }
28 
29 int main()
30 {
31     int u,v;
32     while(~scanf("%d",&n)){
33         g.clear();
34         g.resize(n+2);
35         for(int i=1;i<n;i++){
36             scanf("%d%d",&u,&v);
37             g[u].push_back(v);
38             g[v].push_back(u);
39         }
40         FILL(mark,false);
41         dfs(1,-1);
42         for(int i=1;i<=n;i++)if(mark[i])printf("%d
",i);
43     }
44     return 0;
45 }

View Code