题解 CF219D 【Choosing Capital for Treeland】

An_Account

2018-01-29 19:12:08

Solution

树形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$。代码如下。 ```cpp #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"); } } ```