CodeForces - 219D Choosing Capital for Treeland(树形dp)

#includeusing namespace std;

#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f

const int maxn=4e5+10;

struct edge{
    int u,v,w,next;
}e[maxn];

int g[maxn],tot=0;

int dp[maxn][2],vis[maxn];

void creat_edge(int u,int v,int w)
{
    e[++tot]=(edge){u,v,w,g[u]};
    g[u]=tot;
}

void dfs(int u)
{
    vis[u]=1;
    for(int i=g[u];i>0;i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(vis[v]) continue;
        dfs(v);
        dp[u][0]+=dp[v][0]+w;
    }
}

void dfs1(int u)
{
    vis[u]=1;
    for(int i=g[u];i>0;i=e[i].next)
    {
        int v=e[i].v,w=e[i].w;
        if(vis[v]) continue;
        dp[v][1]+=dp[u][1]+dp[u][0]-dp[v][0]-w+(w?0:1);
        dfs1(v);
    }
    dp[u][1]+=dp[u][0];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        creat_edge(u,v,0);
        creat_edge(v,u,1);
    }
    mem(vis,0);
    dfs(1);
    mem(vis,0);
    dfs1(1);
    int ans=inf;


//    for(int i=1;i//    {
//        cout//    }cout//
//    for(int i=1;i//    {
//        cout//    }cout

    for(int i=1;i)
    {
        if(dp[i][1]ans)
            ans=dp[i][1];
    }
    coutendl;
    int f=1;
    for(int i=1;i)
    {
        if(dp[i][1]==ans)
        {
            if(!f) cout" ";
            couti;
            f=0;
        }
    }
    return 0;
}