题解 CF219D 【Choosing Capital for Treeland】
An_Account
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$。代码如下。
```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");
}
}
```