学步园

http://blog.csdn.net/acm_ted/article/details/7922132

题意：给你一个有向的树，让你选择一个点使得通过反向一些边让这点能到所以其他的点，同时让需要反向的边最少。

题解：两次树形DP，第一次求子树需要反向的边，第二次累加父树以上需要反向的边，取和的最小值即为答案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 200005
int edge[MAX<<1];//表示第i条边的终点
int next[MAX<<1];//与第i条边同起点的下一条边的位置
int head[MAX<<1];//以i为起点的第一条边的储存位置
int to[MAX<<1];
int dp[MAX],dpx[MAX];
void insert(int i,int a,int b,int c)//a起点,b终点
{
    edge[i]=b;
    next[i]=head[a];
    to[i]=c;
    head[a]=i;
}
void dfs_f(int x,int p)//统计子树的修改次数
{
    dp[x]=0;
    for(int i=head[x];i!=-1;i=next[i])
    {
        int k=edge[i];
        if(k==p) continue;
        dfs_f(k,x);
        dp[x]+=(dp[k]+(to[i]==x));
    }
}
void dfs_m(int x,int p,int idx)
{
    if(p==-1) dpx[x]=dp[x];
    else
    {
        if(to[idx]==x) dpx[x]=dpx[p]+1;
        else           dpx[x]=dpx[p]-1;
    }
    for(int i=head[x];i!=-1;i=next[i])
    {
        int k=edge[i];
        if(k==p) continue;
        dfs_m(k,x,i);
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(next,-1,sizeof(next));
    int n,a,b;
    scanf("%d",&n);
    for(int i=1,j=1;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        insert(j++,a,b,b);
        insert(j++,b,a,b);
    }
    dfs_f(1,-1);
    dfs_m(1,-1,1);
    int maxx=0xfffff;
    for(int i=1;i<=n;++i)
        if(dpx[i]<maxx) maxx=dpx[i];
    printf("%d\n",maxx);
    for(int i=1;i<=n;++i)
        if(dpx[i]==maxx)
           printf("%d ",i);
    return 0;
}