D. Choosing Capital for Treeland - 题解

比赛与标签

比赛: Codeforces Round 135 (Div. 2) 标签: dfs and similar, dp, graphs, trees 难度: *1700

喵喵，题目说什么呀？

主人你好呀~ 这道题目是关于一个叫做 Treeland 的神奇国度的说！(ฅ'ω'ฅ)

这个国家有 n 个城市和 n-1 条 单向 的道路。一个很重要的信息是，如果我们不考虑道路的方向，这些城市和道路就构成了一棵树哦，也就是说从任何一个城市出发都能到达其他任何城市。

现在，长老们要选一个城市作为首都。如果城市 a 被选为首都，那么为了方便长老们出行，所有的道路都必须调整方向，使得从首都 a 出发，可以顺着道路到达其他所有城市。也就是说，所有道路都要指向远离首都的方向。

为了实现这个目标，我们可能需要把一些道路的方向反转过来。每反转一条道路都需要一些成本。我们的任务就是，帮助长老们找到一个最棒的首都，使得需要反转的道路数量最少。

最后，我们要输出两行：

1. 这个最少的反转次数。
2. 所有可以作为首都并达到这个最少次数的城市编号，要按从小到大的顺序排列呐。

如何找到最佳首都捏？

一看到这种在树上为每个节点计算一个“最优值”的问题，本喵的直觉就告诉我，这一定是树形DP大显身手的时候了，喵~

如果我们暴力地为每个城市都计算一遍当它作为首都时的反转次数，每次计算都需要遍历整棵树，总时间复杂度就是 O(N²)，对于 N 高达 2·10⁵ 的数据量来说，肯定会超时的说。

所以，我们需要更聪明的办法！这就是大名鼎鼎的 换根DP (Re-rooting DP) 啦！这种方法超级适合解决这类问题，只需要两次遍历整棵树就可以搞定，是不是很神奇？(✪ω✪)

整个过程分为两步喵：

第一步：先随便选个根，算出它的答案

我们先不纠结哪个城市当首都最好，就随便选一个，比如说 1 号城市，假定它就是首都。

然后我们做一次 DFS 或者 BFS，从 1 号节点出发遍历整棵树。在遍历的过程中，我们可以计算出如果 1 号城市是首都，需要反转多少条道路。

怎么计算呢？对于树上的任意一条边，如果它的方向是 指向 我们选定的根节点 1 的，那它就需要被反转。反之，如果它的方向是 背离 根节点 1 的，那它就是我们想要的，不需要反转。

我们只需要遍历所有 n-1 条边，统计一下有多少条是指向 1 号节点方向的，它们的总和就是 dp[1] 的值啦！dp[i] 在这里就表示选择城市 i 作为首都时需要反转的道路数。

第二步：换根大法，O(1) 推出其他点的答案

有了 dp[1]，我们怎么快速得到其他所有节点的 dp 值呢？

想象一下，我们现在要把首都从父节点 u “移动”到它的一个直接相连的子节点 v。这时候，绝大多数道路的“理想方向”是不会变的。唯一受到影响的，就是连接 u 和 v 的这条边！

• 当 u 是首都时，理想方向是 u -> v。
• 当 v 是首都时，理想方向是 v -> u。

我们来分析一下这条边的代价变化：

1. 如果原始道路是 u -> v：
   • 以 u 为首都时，这条边方向正确，对反转次数贡献为 0。
   • 换成以 v 为首都时，这条边方向错误，需要反转，贡献变为 1。
   • 所以，从 dp[u] 到 dp[v]，代价变化是 +1。
2. 如果原始道路是 v -> u：
   • 以 u 为首都时，这条边方向错误，需要反转，对反转次数贡献为 1。
   • 换成以 v 为首都时，这条边方向正确，贡献变为 0。
   • 所以，从 dp[u] 到 dp[v]，代价变化是 -1。

总结一下，dp[v] = dp[u] + (代价变化)。这个代价变化只跟 u-v 这条边的原始方向有关。

我们可以用一个很巧妙的公式来统一这两种情况。在代码实现里，我们可以用 cost 来表示这条边是否需要反转。比如从 u 到 v，如果原始方向是 u -> v，我们记 cost(u,v) = 0；如果原始方向是 v -> u，我们记 cost(u,v) = 1。那么状态转移方程就是： dp[v] = dp[u] - cost(u,v) + cost(v,u) 因为 cost(u,v) 和 cost(v,u) 一个是0一个是1，所以 cost(v,u) = 1 - cost(u,v)。 代入一下，就得到 dp[v] = dp[u] - cost(u,v) + (1 - cost(u,v)) = dp[u] + 1 - 2 * cost(u,v)。 这个公式是不是超级优雅，喵~

于是，我们就可以从第一次选的根节点 1 开始，再做一次 DFS/BFS，根据这个公式，从父节点的 dp 值 O(1) 地推算出所有子节点的 dp 值。

第三步：收集答案

当第二次遍历结束后，dp 数组里就存着所有城市作为首都时的反转次数啦。我们只需要找到 dp 数组里的最小值，然后把所有 dp 值等于这个最小值的城市编号收集起来，排个序，就可以愉快地输出答案了！

代码是这样写的喵~

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // 使用邻接表来存图，pair<int, int> 分别是 {邻居节点, 代价}
    // s -> t 这条路，从 s 到 t 的代价是 0 (不用反转)
    // 但从 t 到 s 就需要反转，代价是 1
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int s, t;
        cin >> s >> t;
        graph[s].push_back({t, 0}); // s -> t, cost = 0
        graph[t].push_back({s, 1}); // t -> s, cost = 1 (需要反转)
    }

    // dp[i] 表示以城市 i 为首都时，需要反转的道路数
    vector<int> dp(n + 1, 0);
    vector<int> parent(n + 1, -1);
    vector<bool> visited(n + 1, false);
    queue<int> q;

    // --- 第一次遍历：以节点1为根，计算 dp[1] 的值 ---
    // 这里的实现方式是先用BFS构建一棵以1为根的树，并顺便计算dp[1]
    q.push(1);
    visited[1] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int c = edge.second; // c=1 表示 v->u, c=0 表示 u->v
            if (v == parent[u]) continue; // 避免走回父节点
            
            // 建立父子关系，为第二次遍历做准备
            parent[v] = u; 
            visited[v] = true;
            
            // 如果 c=1，说明原始边是 v->u，对于以1为根的树，这条边需要反转
            // 我们把所有需要反转的边的代价累加到 dp[1]
            dp[1] += c; 
            q.push(v);
        }
    }

    // --- 第二次遍历：进行换根DP，计算所有节点的答案 ---
    // 同样用BFS来遍历，从根节点1开始，推导所有子节点的dp值
    vector<bool> visited2(n + 1, false);
    queue<int> q2;
    q2.push(1);
    visited2[1] = true;
    while (!q2.empty()) {
        int u = q2.front();
        q2.pop();
        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int c = edge.second; // 从 u 走向 v 的代价
            if (visited2[v]) continue; // 已经计算过dp值的节点就跳过
            
            visited2[v] = true;
            // 核心换根DP公式！
            // 如果 u->v (c=0)，则 dp[v] = dp[u] + 1
            // 如果 v->u (c=1)，则 dp[v] = dp[u] - 1
            // 合并起来就是 dp[v] = dp[u] + 1 - 2*c
            dp[v] = dp[u] + 1 - 2 * c;
            q2.push(v);
        }
    }

    // --- 找出最小代价和所有对应的首都 ---
    // 使用 min_element 找到 dp 数组中的最小值 (跳过 dp[0])
    int min_val = *min_element(dp.begin() + 1, dp.end());
    
    vector<int> candidates;
    for (int i = 1; i <= n; ++i) {
        if (dp[i] == min_val) {
            candidates.push_back(i);
        }
    }
    // 题目要求按升序输出
    sort(candidates.begin(), candidates.end());

    cout << min_val << '\n';
    for (int i = 0; i < candidates.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << candidates[i];
    }
    cout << '\n';

    return 0;
}

复杂度分析喵

• 时间复杂度: O(N) 的说。我们构建邻接表需要 O(N) 时间。之后进行了两次完整的图遍历（BFS），每次遍历都访问每个节点和每条边一次，所以是 O(N + N-1) = O(N)。最后寻找最小值和收集答案也是 O(N)。排序答案需要 O(k log k)，其中 k 是最优首都的数量。总的来说，主要部分是线性的，所以整体复杂度是 O(N + k log k)，非常高效！
• 空间复杂度: O(N) 的说。我们需要空间来存储邻接表 graph、dp 数组、parent 数组和 visited 数组，这些都需要 O(N) 的空间。BFS 使用的队列最多也只会装下 O(N) 个节点。

知识点与总结的说~

这道题真是一道非常经典的换根DP入门好题呢，喵~ 通过它我们可以学到：

1. 换根DP思想: 当题目要求对树上每个节点都计算一个答案，而这个答案又和它作为根节点的树的结构有关时，就要想到换根DP！它的核心就是“两遍扫描法”：

   • 第一遍扫描 (DFS/BFS): 任选一个根，自底向上（或在遍历中）计算出这个根的答案以及一些子树信息。
   • 第二遍扫描 (DFS/BFS): 自顶向下，利用父节点的答案和之前收集的信息，在 O(1) 时间内推导出子节点的答案。

2. 巧妙的状态转移: dp[v] = dp[u] + 1 - 2 * c 这个公式非常简洁地概括了从父节点转移到子节点时代价的变化，是本题解法的精髓所在。

3. 图的表示技巧: 在邻接表中不仅存储邻居，还附带一个 cost 信息，用来表示边的方向性，这种小技巧在图论问题中非常实用，能让代码更简洁清晰。

希望这篇题解能帮到主人哦！以后遇到类似的树上问题，也要记得本喵教你的换根大法呀！加油，你一定可以的！(づ｡◕‿‿◕｡)づ