poj2378(树的dfs)

题意：给一个树状图，有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*2];
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/2)flag=false;
    }
    if(n-num[u]>n/2)flag=false;
    if(flag)vis[u]=1;
}
int main()
{
    int u,v;
    while(scanf("%d",&n)>0)
    {
        tot=0;
        memset(head,-1,sizeof(head));clr(vis);
        for(int i=1;i<=n;i++)num[i]=1;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1,-1);
        int flag=0;
        for(int i=1;i<=n;i++)if(vis[i])printf("%d
",i),flag=1;
        if(!flag)puts("NONE");
    }
}

View Code