题解 CF219D 【Choosing Capital for Treeland】

2018-01-29 19:12:08


树形dp。题目中的边是单向边,但实际存的时候我们可以双向存储这条边,用一个bool型变量w来表示,看做这条边的权值(0为正向,1为反向)。假如第i个点选为首都,那么i不仅可以到它的子节点,还可以到它的祖先。在第一次自底向上的dfs中,我们用dp[u]表示以u节点为首都时,u到所有子节点S需要逆转的边数。很容易可以得出它的状态转移方程为$dp[u]=\sum(dp[S]+w[i,S])$。在第二次自顶向下的dfs中,dp[i]的定义变成了u到全树节点需要逆转的边数。假如f是u的父亲,那么当f->u这条边是正向的时候,以u为首都则需要将这条边逆转,$dp[u]+=dp[f]+1$。当f->u这条边是反向的时候,以u为首都不需要将这条边逆转,但由于u是f的子节点,因此在dp[f]中将这条边逆转了,所以$dp[u]+=dp[f]-1$。代码如下。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct edge {
    int to,next;
    bool w;
}e[400010];
int head[200010],cnt,dp[200010];
inline void adde(int from,int to,bool w) {//加边
    e[++cnt]=(edge){to,head[from],w};
    head[from]=cnt;
}
void dfs1(int u,int f) {//第一次dfs:求出u到子节点需要逆转的边数
    for (int i=head[u];i;i=e[i].next) 
        if (e[i].to!=f) {
            dfs1(e[i].to,u);
            dp[u]+=dp[e[i].to]+e[i].w;
        }
}
void dfs2(int u,int f) {//第二次dfs:求出u到全树需要逆转的边数
    for (int i=head[u];i;i=e[i].next)
        if (e[i].to!=f) {
            dp[e[i].to]=dp[u]+(e[i].w?-1:1);
            dfs2(e[i].to,u);
        }
}
int main() {
    int n,a,b;
    while (~scanf("%d",&n)) {
        cnt=0;
        memset(head,0,sizeof(head));
        for (int i=1;i<=n-1;i++) {
            scanf("%d%d",&a,&b);
            adde(a,b,false);adde(b,a,true);//双向加边
        }
        memset(dp,0,sizeof(dp));
        dfs1(1,-1);dfs2(1,-1);
        int Min=99999999;
        for (int i=1;i<=n;i++) if (Min>dp[i]) Min=dp[i];
        printf("%d\n",Min);
        for (int i=1;i<=n;i++) if (Min==dp[i]) printf("%d ",i);
        printf("\n");
    }
}