D. Balanced Tree 题解

题目描述

给定一棵有 $n$ 个节点的树，第 $i$ 个节点有一个初始值范围 $[l_i, r_i]$。你需要为每个节点选定初始值 $a_i \in [l_i, r_i]$。

你可以执行任意多次以下操作：

• 选择两个节点 $u, v$（$u$ 可与 $v$ 相同），以 $u$ 为整棵树的根，将 $v$ 的子树中所有节点的值增加 $1$。

目标是通过若干次操作，使所有节点的最终值相等（称为“平衡”），并求出平衡时的最小可能值。注意：只需最小化最终值，无需最小化操作次数。

数据范围

• 测试用例数 $t \le 10^5$
• 单用例节点数 $n \le 2 \times 10^5$，所有用例 $\sum n \le 2 \times 10^5$
• $0 \le l_i \le r_i \le 10^9$

---

思路分析

操作的本质

若以任意节点为根，操作「以 $u$ 为根，增加 $v$ 的子树」等价于：我们可以独立地增加树中任意一个连通块的值。具体来说，对于任意一条边 $(x, y)$，我们既可以增加 $x$ 一侧的连通块（以 $y$ 为根，操作 $x$ 的子树），也可以增加 $y$ 一侧的连通块。

因此，当我们选定一组初始值 $a_i$ 后，可以通过增加某些连通块来消除节点间的差值，最终达到一个全局值 $A \ge \max a_i$。每条边两侧连通块的最大值差异，必须通过增加较小一侧来弥补，而这些弥补量将直接决定 $A$ 的最小值。

贪心 DP 设计

考虑以节点 $0$ 为根，自底向上进行 DP。对每个节点 $u$，定义 $a_u$ 表示 $u$ 在其子树范围内被调整到的值（不是最终全局值）。我们要求 $a_u$ 满足 $l_u \le a_u \le r_u$，并且为了使全局值尽量小，应当让 $a_u$ 尽可能大，以减少向父节点传递的差值。

令 $mx$ 为 $u$ 的所有子节点 $a_v$ 的最大值。显然 $u$ 的值不能低于任意子节点的值（否则无法通过只增加另一侧来抹平差距），因此 $a_u \ge mx$。同时，$a_u$ 也不能低于 $l_u$，也不能高于 $r_u$。综合得到：

• $a_u = \min(\max(mx, l_u), r_u)$

对于每条边 $(u, v)$（$v$ 是 $u$ 的子节点），若 $a_v > a_u$，那么为了平衡这一侧，我们必须将 $u$ 所在的另一侧（或整棵树的其他部分）的值增加 $a_v - a_u$，这将直接贡献到最终全局值中。因此，答案累加 $\max(0, a_v - a_u)$。

最终，根节点 $0$ 没有父节点，其本身的值 $a_0$ 也是全局值的基础组成部分，因此总答案为：

$$\text{ans} = a_0 + \sum_{u} \sum_{v \in \text{son}(u)} \max(0, a_v - a_u) $$

算法步骤

1. 读取 $n$ 及每个节点的 $l_i, r_i$。
2. 建无向图，以 $0$ 为根进行 DFS（通过删除反向边转为有根树）。
3. 自底向上计算：
   • 初始化 $mx = l_u$
   • 对每个子节点 $v$：
     • 递归计算 $a_v$
     • $mx = \max(mx, a_v)$
   • $a_u = \min(mx, r_u)$
   • 对每个子节点 $v$，累加 $\max(0, a_v - a_u)$ 到答案
4. 输出 $ans + a_0$。

时间复杂度 $O(n)$，总复杂度 $O(\sum n)$，可以轻松通过。

---

代码实现

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> l(n), r(n), a(n);
        for (int i = 0; i < n; ++i)
            cin >> l[i] >> r[i];
        
        vector<vector<int>> e(n);
        for (int i = 1; i < n; ++i) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
        
        long long ans = 0;
        function<void(int)> dfs = [&](int u) {
            int mx = l[u];
            for (int v : e[u]) {
                // 删除反向边，防止重复访问父节点
                auto it = find(all(e[v]), u);
                if (it != e[v].end()) e[v].erase(it);
                dfs(v);
                mx = max(mx, a[v]);
            }
            a[u] = min(mx, r[u]);
            for (int v : e[u])
                ans += max(0, a[v] - a[u]);
        };
        dfs(0);
        cout << ans + a[0] << '\n';
    }
    return 0;
}

---

样例说明

以题目第一个样例为例（已转化为 $0$-indexed）：

n = 4
l, r:
0: 0 11
1: 6 6
2: 0 0
3: 5 5
边：
1-0   (原2-1)
2-0   (原3-1)
3-2   (原4-3)

以节点 $0$ 为根，执行 DFS：

• 节点 $3$（叶）：$l=5, r=5$，$mx=5$，$a_3=5$。
• 节点 $2$：$l=0, r=0$，子节点 $3$ 的 $a_3=5$，$mx=\max(0,5)=5$，$a_2=\min(5,0)=0$，贡献 $\max(0, 5-0)=5$。
• 节点 $1$（叶）：$l=6, r=6$，$mx=6$，$a_1=6$，贡献 $0$。
• 节点 $0$：$l=0, r=11$，子节点 $1(a=6)$ 和 $2(a=0)$，$mx=\max(0,6,0)=6$，$a_0=\min(6,11)=6$，贡献 $\max(0,6-6)+\max(0,0-6)=0$。

累计贡献 $ans=5$，最终答案 $ans + a_0 = 5 + 6 = 11$，与样例输出一致。

---

总结

本题通过树上贪心 DP，利用操作可增加任意连通块的性质，自底向上合并子节点信息，并尽量让每个节点取到其允许范围内的最大值，从而最小化必要的全局提升量。代码简洁高效，适用于 $\sum n \le 2\times 10^5$ 的大规模数据。