F. Gardening Friends - 题解

比赛与标签

比赛: Codeforces Round 867 (Div. 3) 标签: brute force, dfs and similar, dp, graphs, trees 难度: *1700

喵喵，题目在说什么呀？

你好呀，我是乐于助人的猫娘！这道题其实超有趣的，我们一起来看看吧~

有两个好朋友，Alisa 和 Yuki，她们种了一棵有 n 个节点的树。一开始，树的根在节点 1。树上每条边的长度都是 k。

她们可以花 c 个金币，把当前的根节点移动到它的一个邻居那里去。这个操作可以做任意次。

一棵树的“价值”，被定义为从根节点到树上所有节点的最大距离。她们的目标是最大化“利润”，利润的计算公式是：

利润 = 树的价值 - 移动根节点花费的总金币

我们需要帮她们找到，通过选择一个最优的节点作为新根，能获得的最大利润是多少，喵~

简单来说，就是我们可以选择树上的任意一个节点 i 作为新的根。

把根从 1 移动到 i，需要花费 dist(1, i) * c 的金币，其中 dist(1, i) 是节点 1 和 i 之间的路径上的边数。
当根在 i 时，树的价值是 max_dist(i) * k，其中 max_dist(i) 是从 i 出发到树上最远节点的边数。
所以，如果我们选择 i 作为新根，利润就是 max_dist(i) * k - dist(1, i) * c。

我们的任务就是在所有 i（从 1 到 n）中，找到使这个利润最大的那个值，的说！

本猫娘的思路分析喵~

要最大化利润，最直接的想法就是——把每个节点都当成根试一遍！然后计算出每个选择对应的利润，取最大的那个就好啦，呐。

公式是 max(max_dist(i) * k - dist(1, i) * c) for i in 1...n。

我们来把这个公式拆解成两部分来计算：

移动成本 dist(1, i) * c: 这个很简单喵！dist(1, i) 就是从初始根节点 1 到目标根节点 i 的最短路径上的边数。因为是树，路径唯一，而且所有边权都一样（可以看作是1），所以我们可以用一次 广度优先搜索（BFS） 从节点 1 开始，就能在 O(n) 的时间内算出 1 到所有其他节点的距离 d1[i] 啦。
树的价值 max_dist(i) * k: 这部分稍微有点挑战性！max_dist(i) 是当 i เป็น根时，i 到树上最远节点的距离（用边数衡量）。这个值在图论里有个专门的名字，叫做节点的 偏心距 (eccentricity)。
如果我们对每个节点 i 都跑一次 BFS/DFS 来找它的最远点，那总复杂度就是 O(n*n)，对于 n 高达 2*10^5 的数据来说，肯定会超时的说！(｡>ω<｡)
所以，我们需要一个更高效的方法来计算所有节点的偏心距。这时候，树形DP（或者叫“二次扫描与换根法”）就闪亮登场啦！这是一个在 O(n) 时间内解决这类问题的经典技巧。
整个过程分为两步（两次DFS）：
- 第一次DFS (dfs1): 我们先随便选个根（比如就用节点 1），从上到下进行DFS。对于每个节点 u，我们计算一个 down[u] 值，它表示 从 u 出发，只能往其子树方向走，能到达的最长路径长度（边数）。这个很容易计算：down[u] = 1 + max(down[v])，其中 v 是 u 的所有孩子节点。如果 u 是叶子，down[u] 就是 0。
- 第二次DFS (dfs2): 这次我们还是从节点 1 开始，从上到下进行DFS。对于每个节点 u，我们计算一个 up[u] 值，它表示 从 u 出发，不经过其子树（即向上走），能到达的最长路径长度。u 的 up 值怎么来呢？这条路径肯定是先从 u 走到它的父节点 p，然后从 p 出发走一条不经过 u 的最长路径。这条从 p 出发的路径有两种可能：
  1. 继续向上走，也就是 p 的 up 路径。
  2. 从 p 走向它的另一个孩子 v' 的子树。所以，up[u] 的值依赖于 up[p] 和 u 的兄弟节点的 down 值。具体来说，up[u] = 1 + max(up[p], longest_path_from_p_to_sibling_subtree)。
当 dfs1 和 dfs2 都完成后，对于任何一个节点 i，从它出发的最长路径，要么是完全在它（以1为根时）的子树里（长度为 down[i]），要么是向上走的（长度为 up[i]）。所以，节点 i 的偏心距就是 max(down[i], up[i])！
最终的完美计划喵~
1. 从节点 1 跑一次BFS，计算出所有 d1[i]。
2. 从节点 1 跑一次 dfs1，计算出所有 down[i]。
3. 从节点 1 跑一次 dfs2，计算出所有 up[i]。
4. 遍历所有节点 i 从 1 到 n，计算利润 max(down[i], up[i]) * k - d1[i] * c。
5. 找到最大的那个利润，就是我们的答案啦！
整个过程的复杂度是 O(n) + O(n) + O(n) = O(n)，非常高效，可以通过本题！

魔法代码大公开！

cpp

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

// 为了方便竞赛编程，我们直接使用std命名空间~
using namespace std;

// 这些变量是针对单个测试用例的，由solve函数管理。
// 把它们放在这里，就像全局变量一样，避免在函数间传来传去。
int n;
vector<vector<int>> adj; // 邻接表，存储树的结构
vector<long long> d1;    // d1[i] 存储从初始根节点1到节点i的距离（边数）
vector<int> down;        // down[u] 表示从u出发，向其子树走的最长路径长度
vector<int> up;          // up[u] 表示从u出发，不向其子树走的最长路径长度

// 第一次DFS，用来计算 down 值
// down[u] 是从节点 u 开始并进入其子树的最长路径的长度。
void dfs1(int u, int p) {
    down[u] = 0; // 初始化
    for (int v : adj[u]) {
        if (v == p) continue; // 不往父节点走
        dfs1(v, u);
        // u到子树的最长路径 = 1 (边u-v) + v到它子树的最长路径
        down[u] = max(down[u], 1 + down[v]);
    }
}

// 第二次DFS，用来计算 up 值
// up[u] 是从节点 u 开始且不进入其子树的最长路径的长度。
void dfs2(int u, int p) {
    int max1 = 0, max2 = 0;
    // 找到从u的子节点出发的最长的两条向下的路径
    for (int v : adj[u]) {
        if (v == p) continue;
        int val = 1 + down[v];
        if (val > max1) {
            max2 = max1;
            max1 = val;
        } else if (val > max2) {
            max2 = val;
        }
    }

    // 为每个孩子 v 计算它的 up 值
    for (int v : adj[u]) {
        if (v == p) continue;
        // 从u出发，不经过v的最长路径，有两种可能：
        // 1. 向上走，即 up[u]
        // 2. 向下走到v的兄弟节点，即 longest_sibling_path
        
        // 如果v所在的分支是u最长的向下路径，那么我们只能用第二长的
        int longest_sibling_path = (1 + down[v] == max1) ? max2 : max1;
        // v的up值 = 1 (边v-u) + 从u出发不经过v的最长路径
        up[v] = 1 + max(up[u], longest_sibling_path);
        dfs2(v, u);
    }
}

void solve() {
    long long k, c;
    cin >> n >> k >> c;
    adj.assign(n + 1, vector<int>());
    for (int i = 0; i < n - 1; ++i) {
        int u_node, v_node;
        cin >> u_node >> v_node;
        adj[u_node].push_back(v_node);
        adj[v_node].push_back(u_node);
    }

    // 步骤1：用BFS计算d1，即从初始根(1)到各点的距离
    d1.assign(n + 1, -1);
    queue<int> q;
    
    d1[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d1[v] == -1) {
                d1[v] = d1[u] + 1;
                q.push(v);
            }
        }
    }

    // 步骤2 & 3：计算所有节点的偏心距
    // 我们可以用两次DFS在O(N)内完成。
    // 任意选择一个根（比如1）开始DFS遍历。
    
    // 第一次DFS：计算 down 值
    down.assign(n + 1, 0);
    dfs1(1, 0);

    // 第二次DFS：计算 up 值
    up.assign(n + 1, 0);
    dfs2(1, 0);

    long long max_profit = -5e18; // 初始化为一个非常小的值

    // 步骤4：遍历所有可能的根节点 i，计算最大利润
    for (int i = 1; i <= n; ++i) {
        // 如果根是 i，树的价值 = i的偏心距 * k
        // i的偏心距 = max(down[i], up[i])
        long long tree_cost = (long long)max(down[i], up[i]) * k;
        
        // 操作成本 = 把根从1移到i的成本 = dist(1, i) * c
        long long op_cost = d1[i] * c;
        
        // 利润 = 树的价值 - 操作成本
        max_profit = max(max_profit, tree_cost - op_cost);
    }

    cout << max_profit << endl;
}

int main() {
    // 快速I/O，让程序跑得更快一点~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

时间与空间的魔法消耗~

时间复杂度: O(N) 的说。每个测试用例中，BFS跑一次是 O(N)，两次DFS分别访问每个节点和边一次，也是 O(N)，最后计算利润的循环是 O(N)。所以总的时间复杂度是线性的，非常棒！
空间复杂度: O(N) 的说。主要是邻接表 adj、距离数组 d1、以及 down 和 up 数组占用的空间，它们的大小都和节点数 N 成正比。

猫娘的小课堂时间~

这道题真是太棒了，融合了好几个树上的经典知识点呢！

问题分解: 解决复杂问题的关键一步，就是把复杂的利润公式 max_dist(i) * k - dist(1, i) * c 分解成两个独立的部分：max_dist(i) 和 dist(1, i)，然后分别求解。这让思路清晰了很多，喵！
树的直径与偏心距: max_dist(i) 其实就是节点 i 的偏心距。计算所有节点的偏心距是树形DP的一个经典应用。这个技巧也被称为“二次扫描”或“换根DP”思想的体现。
树形DP (二次扫描法):
- 第一次DFS（自底向上）：收集子树的信息（比如 down 数组）。
- 第二次DFS（自顶向下）：利用父节点和兄弟节点的信息，来完善当前节点的信息（比如 up 数组）。这个方法超级强大，适用于很多需要在树上为每个节点计算一个依赖于全局信息的值的题目。
BFS求最短路: 在无权图（或所有边权相同的图）中，BFS是求单源最短路径的不二之选。这里用它来计算移动成本，简直是天作之合！

总之，当你遇到一个树上的问题，需要对“每个节点作为根”的情况进行讨论时，一定要想想是不是可以用树形DP来优化，避免 O(N^2) 的暴力枚举哦！希望这次的讲解对你有帮助，下次解题再见啦，喵~ (ฅ'ω'ฅ)

F. Gardening Friends - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

本猫娘的思路分析喵~ ​

魔法代码大公开！ ​

时间与空间的魔法消耗~ ​

猫娘的小课堂时间~ ​