題意就是在樹上找一個節(jié)點，刪除后使得各個連通分支的點數不超過總點數的1/2
還是老方法，先對樹DP一次，求得各個子樹的節(jié)點數，然后再統(tǒng)計一次即可
貼代碼
1
# include <iostream>
2# include <cstdio>
3# include <vector>
4# include <algorithm>
5int n;
6using namespace std;
7vector<int> g[10005];
8int num[10005];
9vector<int> ans;
10int dfs(int pos,int pre)
11
{
12
for(vector<int>::iterator i=g[pos].begin();i!=g[pos].end();i++)
13 if((*i)==pre)
14
{
15 g[pos].erase(i);
16 break;
17
}
18 num[pos]=1;
19 for(int i=0;i<g[pos].size();i++)
20 num[pos]+=dfs(g[pos][i],pos);
21 return num[pos];
22
}
23void cal(int pos)
24{
25 bool flag=true;
26 for(int i=0;i<g[pos].size();i++)
27 {
28 cal(g[pos][i]);
29 if(num[g[pos][i]]>(n>>1))
30 flag=false;
31 }
32 if(pos!=1&&num[1]-num[pos]>(n>>1)) flag=false;
33 if(flag) ans.push_back(pos);
34}
35int main()
36{
37 // freopen("input.txt","r",stdin);
38 // freopen("output.txt","w",stdout);
39 scanf("%d",&n);
40 for(int i=1;i<n;i++)
41 {
42 int u,v;
43 scanf("%d%d",&u,&v);
44 g[u].push_back(v);
45 g[v].push_back(u);
46 }
47 dfs(1,-1);
48 cal(1);
49 sort(ans.begin(),ans.end());
50 if(ans.empty())
51 printf("NONE\n");
52 else
53 for(int i=0;i<ans.size();i++)
54 printf("%d\n",ans[i]);
55 // system("pause");
56 return 0;
57}
58
59