题目链接:http://poj.org/problem?id=2378
题意:给一个树状图,有n个点。求出,去掉哪个点,使得剩下的每个连通子图中点的数量不超过n/2。
分析:num[u]表示以u为根节点的子树的总节点树,判断下与u连接的儿子v代表的子树总节点num[v]和u的父亲代表的子树总节点n-num[u]即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
#define clr(a) (memset(a,0,sizeof(a)))
using namespace std;
struct edge
{
int next,v;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N*];
int head[N],tot,n,m;
int num[N],vis[N];
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void dfs(int u,int fa)
{
bool flag=true;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
num[u]+=num[v];
if(num[v]>n/)flag=false;
}
if(n-num[u]>n/)flag=false;
if(flag)vis[u]=;
}
int main()
{
int u,v;
while(scanf("%d",&n)>)
{
tot=;
memset(head,-,sizeof(head));clr(vis);
for(int i=;i<=n;i++)num[i]=;
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfs(,-);
int flag=;
for(int i=;i<=n;i++)if(vis[i])printf("%d\n",i),flag=;
if(!flag)puts("NONE");
}
}