CF1997D Maximize the Root 题解

题意简述

给定一棵以 $1$ 为根的 $n$ 个节点的树，每个节点 $i$ 有权值 $a_i$。你可以进行任意多次操作：

• 选择一个至少有一个儿子的节点 $v$；
• 将 $a_v$ 增加 $1$；
• 同时，对于 $v$ 子树中的所有其他节点 $u$（即除 $v$ 本身外所有在 $v$ 子树内的节点），将 $a_u$ 减少 $1$。

任何时刻所有节点的权值必须非负。

问：根节点 $1$ 最终能达到的最大值是多少？所有测试用例的 $n$ 总和不超过 $2\times 10^5$。

核心观察

操作的效果是：父节点加 $1$，子树中除父节点外的所有节点都减 $1$。因此，想要让根节点尽可能大，就应当尽量减少根被减的次数；同时，整棵子树中每个节点都不能变成负数，这限制了操作的上限。

于是问题转换为：在保证所有节点非负的前提下，子树中能承受的最小值最大是多少，然后结合根节点自己的初始值得到答案。

定义 $dis_i$

记 $dis_i$ 为：在节点 $i$ 的子树中，除 $i$ 本身以外的所有节点的最小值，经过最优操作后所能达到的最大可能值。

特殊地，对于叶子节点，其子树中没有其他节点，我们约定 $dis_{\text{leaf}} = a_{\text{leaf}}$，因为叶子本身的值就是它“其他节点”的上限（实际上叶子的 $dis$ 用于向上传递）。

转移方程

设节点 $v$，它有一个子节点 $u$（已经计算出 $dis_u$）。我们考虑 $v$ 向 $u$ 所在的子树传递操作。

假设我们以 $v$ 为中心进行 $k$ 次操作，那么：

• 父节点 $v$ 的值变为 $a_v + k$；
• 子树 $u$ 中所有节点的值都减少 $k$，因此子树中原来的最小值 $dis_u$ 会变为 $dis_u - k$。

整个部分的最小值为 $\min(a_v + k,\; dis_u - k)$。我们要最大化这个最小值，最优是让两者相等：

$$a_v + k = dis_u - k \quad\Rightarrow\quad k = \frac{dis_u - a_v}{2} $$

此时可达到的最小值为：

$$\frac{a_v + dis_u}{2}$$

由于节点值为整数，且我们关心的是最小值，故取整方式为向下取整，即 $\left\lfloor \dfrac{a_v + dis_u}{2} \right\rfloor$。

若 $a_v \ge dis_u$，则不需要任何操作，最小值只能是 $dis_u$。

综上，对于单个儿子的情况：

• 若 $a_v \ge dis_u$，则 $dis_v$ 候选值为 $dis_u$；
• 否则 $a_v < dis_u$，候选值为 $\left\lfloor \dfrac{a_v + dis_u}{2} \right\rfloor$。

若 $v$ 有多个儿子，由于一次操作会同时影响所有子树，因此只能取所有候选值中的最小值：

$$dis_v = \min_{u \in \text{son}(v)} \text{candidate}(v, u) $$

根节点的特殊处理

根节点没有父节点，无法作为操作中心（题目要求选择的 $v$ 必须有儿子）。因此根节点不会通过操作增加，只可能被后代的操作减少。对于根节点：

• 它从儿子子树中获得的候选值就是各个 $dis_u$；
• 最终 $dis_1 = \min_{u \in \text{son}(1)} dis_u$。

最终答案

当所有节点的 $dis$ 计算完毕后，整棵树的非根节点都能达到至少 $dis_1$ 的最小值，而此时根节点可以保持自己不被过度减少。可以证明，根节点的最大可能值就是：

$$\text{ans} = a_1 + dis_1$$

直观理解：我们可以通过操作使子树中最小值恰好达到 $dis_1$，同时根节点除了承受必要的减少外没有多余的损失，最终根的值就是 $a_1$ 与被保留的最小值 $dis_1$ 之和。

实现方法：拓扑排序

可以从叶子向根的方向进行拓扑排序：

1. 建图时，从每个节点向父节点连边，并统计父节点的入度（即儿子个数）。
2. 初始将入度为 $0$ 的节点（叶子）加入队列，并令 $dis_i = a_i$。
3. 当队列非空，取出节点 $t$，沿边找到其父节点 $v$，用上面的规则更新 $dis_v$：
   • 若 $v = 1$（根），则 $dis_1 \leftarrow \min(dis_1, dis_t)$；
   • 否则，如果 $dis_t \ge a_v$，则 $dis_v \leftarrow \min(dis_v,\ (dis_t + a_v)/2)$；
   • 否则 $dis_v \leftarrow \min(dis_v,\ \min(dis_t, a_v))$。
4. 更新后将父节点的入度减 $1$，如果入度变为 $0$ 则入队。
5. 最终输出 $dis_1 + a_1$。

该过程本质是一个自底向上的 DP，时间复杂度 $O(n)$。

注意事项

• 多测时务必清空所有数组和队列。
• $dis$ 初始化为一个很大的值（如 $0x3f3f3f3f3f3f3f3f$）。
• 数据范围：$a_i$ 最大 $10^9$，$n$ 总和不超 $2\times 10^5$，无需 long long？代码中使用了 int long long 保证安全。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 200005;
int a[MAXN], dis[MAXN], in[MAXN];
int head[MAXN], num;
struct Edge {
    int v, next;
} edge[MAXN];
queue<int> q;

void add(int u, int v) {
    edge[++num].next = head[u];
    head[u] = num;
    edge[num].v = v;
}

void tupo() {
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (t == 1) continue;  // 根本身不会被出边指向，但安全起见
        for (int i = head[t]; i; i = edge[i].next) {
            int v = edge[i].v;       // 父节点
            if (dis[t] >= a[v]) {
                if (v == 1)
                    dis[v] = min(dis[v], dis[t]);
                else
                    dis[v] = min(dis[v], (dis[t] + a[v]) / 2);
            } else {
                if (v == 1)
                    dis[v] = min(dis[v], dis[t]);
                else
                    dis[v] = min(dis[v], min(dis[t], a[v]));
            }
            in[v]--;
            if (!in[v]) q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        while (!q.empty()) q.pop();
        num = 0;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            head[i] = 0;
            in[i] = 0;
            dis[i] = 0x3f3f3f3f3f3f3f3fLL;
        }
        for (int i = 2; i <= n; i++) {
            int p;
            cin >> p;
            add(i, p);   // 子节点连向父节点
            in[p]++;
        }
        // 叶子入队
        for (int i = 2; i <= n; i++) {
            if (in[i] == 0) {
                q.push(i);
                dis[i] = a[i];
            }
        }
        tupo();
        cout << dis[1] + a[1] << '\n';
    }
    return 0;
}