E. Kirei Attacks the Estate - 题解

比赛与标签

比赛: Codeforces Round 1027 (Div. 3) 标签: dfs and similar, dp, greedy, trees 难度: *1400

题目大意喵~

Mina-san, konnichiwa! ฅ'ω'ฅ 今天我们要帮助 Kirei 从一个危险的庄园里逃脱哦！

这个庄园可以看作一棵有 n 个节点的树，根节点是 1。每个节点 i 都有一个危险值 a_i。为了成功撤退，Kirei 需要计算出每个节点的“威胁值”。

一个节点 i 的威胁值被定义为：从节点 i 出发，沿着通向根节点的垂直路径，所能得到的最大交替和。

这里的“交替和”是这样计算的：对于一条从 i 开始，经过其父节点 p_i，祖父节点 p_{p_i} 等等的路径，它的交替和就是 a_i - a_{p_i} + a_{p_{p_i}} - ...。路径可以随时停在任何一个祖先节点上。

比如说，对于题目中的例子，从节点 4 出发的垂直路径有：

[4]，交替和为 a_4 = 6
[4, 3]，交替和为 a_4 - a_3 = 6 - 2 = 4
[4, 3, 2]，交替和为 a_4 - a_3 + a_2 = 6 - 2 + 5 = 9
[4, 3, 2, 1]，交替和为 a_4 - a_3 + a_2 - a_1 = 6 - 2 + 5 - 4 = 5

这些和中的最大值是 9，所以节点 4 的威胁值就是 9 啦！

我们的任务就是帮 Kirei 计算出每个节点的威胁值，让他能顺利跑路的说！

解题思路喵~

这道题看起来有点复杂呢，如果对每个节点都暴力枚举它所有的祖先路径，肯定会超时的说！( TωT ) 所以我们需要找到一个更聪明的办法，喵~

关键的转化！

让我们来仔细研究一下这个“交替和”。从节点 i 到它的某个祖先 j 的交替和 T(i, j) 是 a_i - a_{p(i)} + a_{p(p(i))} - ... \pm a_j。这个和的计算依赖于路径的起点 i，非常不方便我们进行统一处理。

能不能找到一个固定的参考点呢？当然是根节点 1 啦！

我们来定义一个从根节点 1 出发的“神奇路径和” S[v]： S[v] = a_1 - a_{p(1)} + a_{p(p(1))} - ... \pm a_v 其中，p(v) 是 v 的父节点，p(p(v)) 是祖父节点。我们规定根节点 1 的深度 dep[1] = 1。那么，S[v] 可以表示为： S[v] = \sum_{k \text{ on path } 1 \to v} (-1)^{dep[k]-1} a_k

这个 S[v] 可以通过一次从根节点开始的遍历（BFS 或 DFS）在 O(N) 时间内计算出来。对于一个节点 v 和它的父节点 u：

如果 dep[v] 是奇数, S[v] = S[u] + a_v
如果 dep[v] 是偶数, S[v] = S[u] - a_v

神奇的联系！

现在，我们来找一下我们想求的 T(i, j) 和刚刚定义的 S[v] 之间的关系。经过一番推导（像小猫玩毛线球一样把公式滚来滚去~），我们可以发现一个惊人的事实！

T(i, j) = (-1)^{dep[i]+1} \times (S[i] - S[p(j)])

这里 p(j) 是 j 的父节点。这个公式的推导有点点绕，但它告诉我们，任意一段向上路径的交替和，都可以用我们预处理的 S 数组的两个值的差来表示！是不是很奇妙呀喵~

分情况讨论！

现在我们的目标是，对于每个节点 i，找到一个祖先 j（j 可以是 i 自己），使得 T(i, j) 最大化。

根据我们得到的公式，可以分成两种情况来讨论：

1. 当 dep[i] 是奇数时：dep[i]+1 是偶数，所以 (-1)^{dep[i]+1} = 1。我们要最大化 T(i, j) = S[i] - S[p(j)]。因为 S[i] 是固定的，所以我们实际上需要最小化 S[p(j)]。p(j) 可以是 i 的任意一个（真）祖先，或者是根节点 1 的“虚拟父节点”（我们可以认为它的 S 值为 0）。所以，我们需要找到从根的虚拟父节点到 i 的父节点路径上所有 S 值的最小值。

2. 当 dep[i] 是偶数时：dep[i]+1 是奇数，所以 (-1)^{dep[i]+1} = -1。我们要最大化 T(i, j) = -(S[i] - S[p(j)]) = S[p(j)] - S[i]。因为 S[i] 是固定的，所以我们实际上需要最大化 S[p(j)]。所以，我们需要找到从根的虚拟父节点到 i 的父节点路径上所有 S 值的最大值。

算法实现

综合以上分析，我们的算法步骤就清晰啦：

从根节点 1 开始进行一次 BFS 遍历。
在遍历过程中，为每个节点 v 计算出它的深度 dep[v] 和神奇路径和 S[v]。
同时，我们维护两个值：
- pre_min[v]: 从根的虚拟父节点（S值为0）到节点 v 的路径上，所有 S 值的最小值。
- pre_max[v]: 从根的虚拟父节点到节点 v 的路径上，所有 S 值的最大值。这两个值可以由父节点的值递推得到： pre_min[v] = min(S[v], pre_min[parent(v)])pre_max[v] = max(S[v], pre_max[parent(v)])
BFS 结束后，我们遍历所有节点 i，根据 dep[i] 的奇偶性，使用上面推导出的逻辑来计算最终答案 ans[i]。
- 如果 dep[i] 是奇数，答案是 S[i] - (i的父节点路径上的S最小值)。这可以巧妙地用 S[i] - pre_min[i] 来计算，主人可以思考一下为什么哦~ (提示: pre_min[i] = min(S[i], pre_min[p(i)]))
- 如果 dep[i] 是偶数，答案是 (i的父节点路径上的S最大值) - S[i]。这同样可以巧妙地用 pre_max[i] - S[i] 来计算。

这样，我们只需要一次遍历就可以解决问题啦，非常高效！

代码实现

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 typedef long long ll;
 int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        vector<vector<int>> graph(n + 1);
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        // dep[i]: 节点i的深度 (根节点深度为1)
        vector<int> dep(n + 1);
        // sum[i]: 从根节点1到节点i的神奇路径和 S[i]
        vector<ll> sum(n + 1);
        // pre_min[i]: 从虚拟根(S=0)到节点i路径上S值的最小前缀和
        vector<ll> pre_min(n + 1);
        // pre_max[i]: 从虚拟根(S=0)到节点i路径上S值的最大前缀和
        vector<ll> pre_max(n + 1);
        vector<bool> visited(n + 1, false);
        
        // 使用BFS进行层序遍历，自顶向下计算所需的值
        queue<int> q;
        q.push(1);
        visited[1] = true;
        
        // 初始化根节点1
        dep[1] = 1;
        sum[1] = a[1];
        // 虚拟根的S值为0，所以pre_min/max的初值要和0比较
        pre_min[1] = min(0LL, sum[1]);
        pre_max[1] = max(0LL, sum[1]);
        
        // BFS 主循环
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : graph[u]) {
                if (visited[v]) continue; // 避免重复访问和访问父节点
                visited[v] = true;
                
                // 计算子节点 v 的各项值
                dep[v] = dep[u] + 1;
                // 根据深度的奇偶性计算 S[v]
                if (dep[v] % 2 == 1) { // 奇数深度，加 a[v]
                    sum[v] = sum[u] + a[v];
                } else { // 偶数深度，减 a[v]
                    sum[v] = sum[u] - a[v];
                }
                // 从父节点 u 递推 pre_min 和 pre_max
                pre_min[v] = min(sum[v], pre_min[u]);
                pre_max[v] = max(sum[v], pre_max[u]);
                
                q.push(v);
            }
        }
        
        // 计算最终答案
        vector<ll> ans(n + 1);
        for (int i = 1; i <= n; i++) {
            if (dep[i] % 2 == 1) { // 奇数深度
                ans[i] = sum[i] - pre_min[i];
            } else { // 偶数深度
                ans[i] = pre_max[i] - sum[i];
            }
        }
        
        // 输出结果
        for (int i = 1; i <= n; i++) {
            cout << ans[i];
            if (i < n) cout << ' ';
            else cout << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度: O(N) 的说。我们使用 BFS 遍历了整棵树，每个节点和每条边都只访问了一次。之后计算答案的循环也是 O(N) 的。对于 T 组数据，总时间复杂度是 O(ΣN)。
空间复杂度: O(N) 的说。我们需要空间来存储树的邻接表、a 数组以及 dep, sum, pre_min, pre_max 等辅助数组，它们的大小都和节点数 N 成正比。

知识点与总结喵！

这道题真是一只披着树皮的数学小猫咪呢！它完美地结合了 树上DP 和 前缀和 的思想。

树上前缀和: 核心思想是将对路径的查询转化为对路径端点处预处理值的计算。这在处理树上路径问题时是一种非常强大的技巧。
问题转化: 面对复杂的计算式，尝试寻找一个不变量或者一个可以递推的量（比如本题的 S[v]），然后建立起目标和这个量之间的关系，是解题的关键一步。
BFS/DFS的应用: 无论是 BFS 还是 DFS，都可以用来完成这种自顶向下的信息传递和预处理工作。BFS 在这里非常自然，因为它按层处理，和深度的概念很契合。
细节处理: "虚拟父节点" 的引入（代码中的 0LL）是一个很棒的技巧，它统一了对根节点和非根节点的处理，让代码变得更加简洁。

希望这篇题解能帮助到你，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！(๑•̀ㅂ•́)و✧

E. Kirei Attacks the Estate - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

关键的转化！ ​

神奇的联系！ ​

分情况讨论！ ​

算法实现 ​

代码实现 ​

复杂度分析 ​

知识点与总结喵！ ​