Description 有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。 Input 第一行：一个整数N (1 <= N <= 10,000)。 后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。 Output 输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行：”NONE”.
分析：任选一个节点作为根生成一棵树。遍历树的时候，令S[i]记录以i为根的树的节点个数。如果一个节点的所有儿子节点的S值不超过总结点数的一半，以及总结点数减去该节点的S值也不超过总节点数的一半，则该节点符合题目条件。
代码
#include <cstdio> #define maxn 100005 using namespace std; int s[maxn],x[maxn],y[maxn],y1[maxn],ls[maxn],ls1[maxn],next[maxn],next1[maxn]; bool fl,f1,f[maxn]; int n,tot,p,q; void add(int p,int q) { tot++; x[tot]=p; y[tot]=q; next[tot]=ls[p]; ls[p]=tot; } int dfs(int p) { f[p]=true; for (int i=ls[p];i;i=next[i]) if (!f[y[i]]) { tot++; next1[tot]=ls1[p]; y1[tot]=y[i]; ls1[p]=tot; s[p]+=dfs(y[i])+s[y[i]]; } return 1; } int main() { freopen("data8.in","r",stdin); scanf("%d",&n); for (int i=1;i<n;i++) { scanf("%d%d",&p,&q); add(p,q); add(q,p); } tot=0; dfs(1); for (int i=1;i<=n;i++) { fl=false; for (int j=ls1[i];j;j=next1[j]) { if (s[y1[j]]+1>n/2) { fl=true; break; } } if (n-s[i]+1>n/2) fl=true; if (!fl) { printf("%d\n",i); f1=true; } } if (!f1) printf("NONE"); }