2017.07.09【NOIP提高组】模拟赛B组 treecut

原题：

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];
}