题目描述

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

---

思路

随便选定一个点作为根节点，建一颗树，同时记录下以当前点为根的树一共有多少节点，每次判断时判断每一个子节点是否超过一半，并判断其他的节点的总数是否超过一半即可

---

#include 
#include 
using namespace std;
#define maxn 100001
struct edge
{
    int to, next;
}e[maxn];
int ls[maxn], f[maxn];
int fl[maxn], v = 0 , tot = 0;
edge e2[maxn];
int ls2[maxn], s[maxn], xx[maxn], n;
int check(int x)
{
    for (int i = ls2[x]; i; i = e2[i].next)
    {
        if (s[e2[i].to] > n / 2) return 0;
    }
    return 1;
}
int ll = 0;
int dfs1(int now, int fa)
{
    fl[now] = 1;
    s[now] = 1;
    for (int i = ls[now]; i; i = e[i].next)
        if (fl[e[i].to] == 0)
        {
            e2[++ll] = (edge) {e[i].to, ls2[now]};
            ls2[now] = ll;
            dfs1(e[i].to, now);
            s[now] += s[e[i].to];
        }
}
int main()
{
    scanf("%d", &n);
    int l = 0;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, ls[y]};
        ls[y] = l;
    }
    dfs1(1, 0);
    for (int i = 1; i <= n; i++)
    {
        if (check(i) && n - s[i] <= n / 2)
            xx[i] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (xx[i]) printf("%d\n", i);
}