原題：

https://jzoj.net/senior/#contest/show/2043/2

題目描述：

有一個(gè)N個(gè)節(jié)點(diǎn)的無(wú)根樹(shù)，各節(jié)點(diǎn)編號(hào)為1..N，現(xiàn)在要求你刪除其中的一個(gè)點(diǎn)，使分割開(kāi)的連通塊中節(jié)點(diǎn)個(gè)數(shù)都不超過(guò)原來(lái)的一半多。

輸入：

第一行：一個(gè)整數(shù)N (1 <= N <= 10,000)。 　　后面有N-1行：每行兩個(gè)整數(shù) X 和 Y，表示一個(gè)邊連接的兩個(gè)節(jié)點(diǎn)號(hào)。

輸出：

輸出所有可能選擇的點(diǎn)。如果有多個(gè)節(jié)點(diǎn)，按編號(hào)從小到大輸出，每個(gè)一行。 如果找不到這樣的點(diǎn)，輸出一行："NONE".

樣例輸入：

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

樣例輸出：

3 8

樣例說(shuō)明：

刪除3號(hào)或8號(hào)節(jié)點(diǎn)，則分枝最多有5個(gè)節(jié)點(diǎn)

分析：

既然是樹(shù)，我們?yōu)榱朔奖憔桶阉捎懈鶚?shù)。
這道題跟節(jié)點(diǎn)數(shù)有關(guān)，我們就可以用一個(gè)DFS來(lái)求出當(dāng)前節(jié)點(diǎn)的兒子樹(shù)

6631287668030149991.jpg

紅色數(shù)字表示這個(gè)節(jié)點(diǎn)作為父親節(jié)點(diǎn)時(shí)的樹(shù)的大小
題目要求，我們要找一個(gè)點(diǎn)，刪除后要求剩下的聯(lián)通塊節(jié)點(diǎn)數(shù)不超過(guò)總數(shù)的一半。
比如，刪除3

1625799465581247064.jpg

實(shí)現(xiàn)：

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