题目传送门

Description

有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。

Input

第一行：一个整数N (1 <= N <= 10,000)。后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。

Output

输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行："NONE".

Sample Input

10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8

Sample Output

3
8

HINT

样例说明：删除3号或8号节点，则分枝最多有5个节点

思路：

万队长讲过的树上问题之一  (真*树形DP)我们先dfs一次，求出所有子树的size ，然后判断：删去一个点i后产生的联通块只能是两种 子树size[to[i]]以及其父树,而父树的size=n-size[i],所以分别判断是否超过n/2即可

这竟然还是一道双倍经验的题QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int head[11000];
int to[22000];
int net[22000];
int size[22000];
int fa[22000];
int n;
void dfs(int x,int temp)
{
    size[x]=1;
    fa[x]=temp;
    for(int i=head[x];i;i=net[i])
    {
        if(to[i]==temp)continue;
        dfs(to[i],x);
        size[x]+=size[to[i]];
    }
}
int tot;
void add(int x,int y)
{
    net[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(1,0);
    bool nmp=false;
    for(int i=1;i<=n;i++)
    {
        bool flag=true;
        if(n-size[i]>n/2)flag=false;
        for(int j=head[i];j;j=net[j])
        {
            if(!flag) break;
            if(to[j]==fa[i])continue;
            if(size[to[j]]>n/2)flag=false;
        }
        if(flag) nmp=true,printf("%d\n",i);
    }
    if(!nmp)printf("NONE");
}