cf 219D Choosing Capital for Treeland 树形dp

一遍dfs找到1节点需要装换的边数，然后再一次dfs求得每个点的值，若i能到j，则dp[j]=dp[i]+1，否则dp[j]=dp[i]-1。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
vector<int> tree[200005];
vector<int> dir[200005];
int dp[200005];
int dfs1(int now,int fa=-1)
{
    int tot=0;
    for(int i=0;i<tree[now].size();i++)
    {
        int to=tree[now][i];
        if(to!=fa)
        {
            tot+=(dfs1(to,now)+(dir[now][i]<0?1:0));
        }
    }
    return tot;
}
void dfs2(int now,int tot,int fa=-1)
{
    dp[now]=tot;
    for(int i=0;i<tree[now].size();i++)
    {
        int to=tree[now][i];
        if(to!=fa)
        {
            dfs2(to,tot+dir[now][i],now);
        }
    }
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int a,b;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
            dir[a].push_back(1);
            dir[b].push_back(-1);
        }
        int t=dfs1(1);
        dfs2(1,t);
        int mins=3000000;
        for(int i=1;i<=n;i++) mins=min(dp[i],mins);
        printf("%d\n",mins);
        for(int i=1;i<=n;i++)
        {
            if(dp[i]==mins)
            {
                printf("%d ",i);
            }
        }
        puts("");
    }
    return 0;
}

cf 219D Choosing Capital for Treeland 树形dp

原文：http://blog.csdn.net/t1019256391/article/details/18530221