题解：P8274 [USACO22OPEN] Balancing a Tree G

_Ikun_xiaoheizi · 2026-08-10 19:51:21 · 题解

竟然还能交题解，那我必须水一发。

思路

考虑一条从根到叶子的路径，路径上所有点两两都有祖先后代关系。因此，这条路径对不平衡度的贡献就是路径上所有 s 值的最大值与最小值之差。整棵树的不平衡度就是所有根到叶路径上极差的最大值。

设 ans 为最小可能的不平衡度，问题转化为：为每个点 i 分配 s_i \in [l_i, r_i]，最小化每条根到叶路径的极差的最大值。

对于任意一条从根到某个节点 i 的路径，设该路径上所有 l 的最大值为 L_i = \max_{j \in {path}(1 \to i)} l_j，所有 r 的最小值为 R_i = \min_{j \in {path}(1 \to i)} r_j。

如果 L_i > R_i，那么在这条路径上，必然存在某个节点被强制取到 \ge L_i 的值，同时另一个节点被强制取到 \le R_i 的值，因此路径上的极差至少为 L_i - R_i。于是有：

设全局最大下界为 \max l = \max_{i=1}^N l_i，全局最小上界为 \min r = \min_{i=1}^N r_i。若 \max l > \min r，设 u 满足 l_u = \max l，v 满足 r_v = \min r。

考虑 u 和 v 的最近公共祖先 w。从 u 到 w 再到 v 的整条路径上，s_u \ge {maxl}，s_v \le {minr}。由于路径上相邻两点的值变化有限，极差至少被“摊平”在这条路径上。可以严格证明，这样的结构必然迫使不平衡度至少为 \lceil \frac{{maxl} - {minr}}{2} \rceil。因此：

上述两个下界的最大值就是最终的答案，

当 \max l \le \min r 时，所有区间有公共交集，此时上述两项均 \le 0，答案就是 0。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005], l[100005], r[100005], f[100005][2];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T, b;
    cin >> T >> b;
    while (T--) {
        memset(f, 0, sizeof(f));
        cin >> n;
        for (int i = 2; i <= n; i++) {
            cin >> a[i];
        }
        int minnr = 2e9, maxxl = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> l[i] >> r[i];
            minnr = min(r[i], minnr);
            maxxl = max(l[i], maxxl);
            if (a[i] != 0) {
                f[i][0] = max(f[a[i]][0], l[i]);
                f[i][1] = min(f[a[i]][1], r[i]);
            } else {
                f[i][0] = l[i];
                f[i][1] = r[i];
            }
            ans = max(ans, f[i][0] - f[i][1]);
        }
        cout << max(ans, (maxxl - minnr + 1) / 2) << endl;
        if (b) {
            if (maxxl <= minnr) {
                for (int i = 1; i <= n; i++) {
                    cout << maxxl << " ";
                }
                continue;
            }
            int mid = (maxxl + minnr) / 2;
            for (int i = 1; i <= n; i++) {
                cout << max(min(mid, r[i]), l[i]) << " ";
            }
        }
    }
    return 0;
}

总感觉写的复杂了点，不管了。