Description

---

给出一个树形图(“tree-shaped” network)，有N(1 <= N <= 10,000)个顶点。如果删除树上某一个顶点，整棵树就会分割成若干个部分。显然，每个部分内部仍保持连通性。

现在问：删除哪个点，使得分割开的每个连通子图中点的数量不超过N/2。如果有很多这样的点，就按升序输出。

例如，如图所示的树形图，砍掉顶点3或者顶点8，分割开的各部件。

Input

---

第1行：1个整数N，表示顶点数。顶点编号1～N

第2..N行：每行2个整数X和Y，表示顶点X与Y之间有一条边

Output

---

若干行，每行1个整数，表示一个符合条件的顶点的编号。如果没有顶点符合条件，则仅在第1行上输出”NONE”

Analysis

---

伪装得很好的一道水题

第一眼看去以为是割点，然而忽略了这是树形图的事实和条件

直接dfs，找到一个入度为1的点作为根节点，dfs一下用f[i]记录i节点的儿子个数

枚举要删的点，分别统计它的子节点、父节点形成的连通块节点数量，判断一下就好了

我才不说根本没有NONE的情况嘞

Code

---

#include 
     
      #include 
      
       using namespace std;struct edge{    int x,y,next;};bool v[200001];edge e[200001];int ls[200001],ind[200001],f[200001],maxE=0,root,max;void add(int x,int y){    e[++maxE]=(edge){x,y,ls[x]};    ls[x]=maxE;}void dfs(int x){    v[x]=true;    if (ind[x]==1&&x!=root)    {        f[x]=1;        return;    }    for (int i=ls[x];i;i=e[i].next)        if (!v[e[i].y])        {            dfs(e[i].y);            f[x]+=f[e[i].y];        }    ++f[x];}int main(){    int n;    scanf("%d",&n);    for (int i=1;i
       
        n/2)                flag=true;        if (!flag&&n-f[i]<=n/2)            printf("%d\n",i);    }    return 0;}