「Codeforces 219D」Choosing Capital for Treeland - 树形 DP

发表于 更新于 分类于 ， 阅读次数： Disqus：

题目描述

Codeforces 链接

Treeland 国有 \(n\) 个城市，这 \(n\) 个城市连成了一颗树，有 \(n - 1\) 条道路连接了所有城市。每条道路只能单向通行。现在政府需要决定选择哪个城市为首都。假如城市 i 成为了首都，那么为了使首都能到达任意一个城市，不得不将一些道路翻转方向，记翻转道路的条数为 \(k\)。你的任务是找到所有满足 \(k\) 最小的首都。

解题思路

这道题我们可以考虑使用树形 DP 解决。

DP 求解

首先我们选定任意一个节点为这棵树的根，这里我们以 \(1\) 节点为例。

接着跑一遍 DP，此时 DP 存储的是从这个节点出发，到达该节点为根的子树中的所有节点所需要最少翻转道路的次数。

显然我们可以推出下列状态转移方程（\(f_i\) 中 \(i\) 表示节点，\(e\) 表示子以 \(i\) 为根的子树中从 \(i\) 出发的边的集合，\(eRev\) 表示子以 \(i\) 为根的子树中指向 \(i\) 的边的集合）：

\[ f_i = \begin{cases} f_j & j \in e \\ f_j + 1 & j \in eRev \end{cases} \]

此时 \(f_1\) 则为以 \(1\) 为首都的答案。

换根

虽然我们可以以每一个点为首都，分别 DP 一次得解，但这种方法的时间复杂度是 \(O(n^2)\)，并不理想。故我们可考虑用其他方法求解。

基于上面以 \(1\) 为首都的 DP，我们可以在此数据上 换根 以求出以其他节点为首都的答案。

对于换根，我们可以从 \(1\) 节点开始跑第二遍 DP。

仍然以 \(1\) 为根，我们初始化 \(g_1 = f_1\)，其中 \(g_i\) 表示以 \(i\) 为首都至少需要翻转多少条道路。

对于节点 \(i\)，若 \(j\) 是 \(i\) 为根的子树中从 \(i\) 出发的边所到达的节点，说明从 \(j\) 到 \(i\) 路是反的，从 \(j\) 到 \(i\) 比从 \(i\) 到 \(j\) 需要多翻转一条边，答案则为 \(g_i + 1\)；

同理，若 \(j\) 是 \(i\) 为根的子树中指向 \(i\) 的边中出发的节点，说明从 \(j\) 到 \(i\) 路是正的，从 \(j\) 到 \(i\) 比从 \(i\) 到 \(j\) 需要少翻转一条边，答案则为 \(g_i - 1\)；

换句话说，我们有下列转移方程：

\[ g_i = \begin{cases} g_j + 1 & j \in e \\ g_j - 1 & j \in eRev \end{cases} \]

对于求 \(g_j\) 的过程，我们可以形象地想象成这棵树的根从 \(i\) 换到了 \(j\)。我们把这种操作称作 换根。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <vector>

const int MAXN = 200000, INF = 0x3f3f3f3f;

int n;
std::vector<int> e[MAXN + 1], eRev[MAXN + 1];
int f[MAXN + 1], ch[MAXN + 1];
bool vis[MAXN + 1];

int dp(int p) {
    if (vis[p]) return f[p];
    vis[p] = true;

    for (int nodes : e[p]) {
        if (!vis[nodes]) {
            f[p] += dp(nodes);
        }
    }

    for (int nodes : eRev[p]) {
        if (!vis[nodes]) {
            f[p] += dp(nodes) + 1;
        }
    }

    return f[p];
}

void dfs(int p) {
    vis[p] = true;

    for (int nodes : e[p]) {
        if (!vis[nodes]) {
            ch[nodes] = ch[p] + 1;
            dfs(nodes);
        }
    }

    for (int nodes : eRev[p]) {
        if (!vis[nodes]) {
            ch[nodes] = ch[p] - 1;
            dfs(nodes);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        e[a].push_back(b);
        eRev[b].push_back(a);
    }

    memset(f, 0, sizeof(f));
    memset(vis, false, sizeof(vis));
    dp(1);

    memset(ch, 0, sizeof(ch));
    memset(vis, false, sizeof(vis));
    ch[1] = f[1];
    dfs(1);

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = std::min(ans, ch[i]);
    }

    printf("%d\n", ans);
    for (int i = 1; i <= n; i++)  {
        if (ch[i] == ans) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}