原题：
https://jzoj.net/senior/#contest/show/2043/2
题目描述：
有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。
输入：
第一行：一个整数N (1 <= N <= 10,000)。 后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。
输出：
输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行："NONE".
样例输入：
10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8
样例输出：
3 8
样例说明：
删除3号或8号节点，则分枝最多有5个节点
分析：
既然是树，我们为了方便就把它弄成有根树。
这道题跟节点数有关，我们就可以用一个DFS来求出当前节点的儿子树
6631287668030149991.jpg
红色数字表示这个节点作为父亲节点时的树的大小
题目要求，我们要找一个点，删除后要求剩下的联通块节点数不超过总数的一半。
比如，删除3
1625799465581247064.jpg
黄色这一块就是父亲节点减去自己，就是10-8=2
红色和蓝色就是3的子树大小。
我们可以通过一个DFS，每步回溯子树大小，判断是否能否删除此节点
实现：
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
int DFS(int);
int DFS_ANS(int);
vector <int> ljlb[10007];
bool used[10007],ans[10007];
int childn[10007];
int i,u,v,n,j,mid;
int main()
{
for (i=0;i<10007;i++) childn[i]=1;
cin>>n;
mid=n>>1;
for (i=0;i<n-1;i++)
{
cin>>u>>v;
ljlb[u].push_back(v);
ljlb[v].push_back(u);
}
used[1]=true;
childn[1]=DFS(1);
memset(used,false,sizeof(used));
used[1]=true;
childn[1]=DFS_ANS(1);
for (i=1;i<=n;i++)
if (!ans[i]) cout<<i<<endl;
}
int DFS(int root)
{
int t=ljlb[root].size();
if (t==0) return 1;
for (int j=0;j<t;j++)
{
if (!used[ljlb[root][j]])
{
used[ljlb[root][j]]=true;
childn[root]+=DFS(ljlb[root][j]);
}
}
return childn[root];
}
int DFS_ANS(int root)
{
if (n-childn[root]>mid) ans[root]=true;
for (int j=0;j<ljlb[root].size();j++)
{
if (!used[ljlb[root][j]])
{
used[ljlb[root][j]]=true;
if (DFS_ANS(ljlb[root][j])>mid) ans[root]=true;
}
}
return childn[root];
}
