首页 > 代码库 > poj2378(dfs,树形dp)

poj2378(dfs,树形dp)

和poj3107,poj1655一样的方法

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 100000000#define eps 1e-8#define pii pair<int,int>#define LL long long intstruct node{    int v,next;}e[100010];int n,a,b,head[50005];int num[50005],bal[50005],cnt=1;void add(int aa,int bb);int dfs1(int x,int fa);void dfs2(int x,int fa);int main(){    //freopen("in1.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%d",&n);    memset(head,-1,sizeof(int)*(n+1));    for(int i=1;i<=n;i++) num[i]=1;    for(int i=1;i<=n-1;i++)    {        scanf("%d%d",&a,&b);        add(a,b);        add(b,a);    }    dfs1(1,-1);    dfs2(1,-1);    for(int i=1;i<=n;i++)    {        if(bal[i]<=n/2)        {            printf("%d\n",i);        }    }    //fclose(stdin);    //fclose(stdout);    return 0;}void add(int aa,int bb){    e[cnt].v=bb;    e[cnt].next=head[aa];    head[aa]=cnt++;}int dfs1(int x,int fa){    for(int i=head[x];i!=-1;i=e[i].next)    {        if(e[i].v==fa)            continue;        else        {            num[x]+=dfs1(e[i].v,x);        }    }    return num[x];}void dfs2(int x,int fa){    for(int i=head[x];i!=-1;i=e[i].next)    {        if(e[i].v==fa)        {            bal[x]=max(bal[x],n-num[x]);        }        else        {            bal[x]=max(bal[x],num[e[i].v]);            dfs2(e[i].v,x);        }    }}