题解 | #最大稳定数值#

一、问题分析

本题的核心在于维护两个动态约束条件。对于任意结点 $u$ ：

上层约束 (Ancestors Condition)：其所有严格祖先结点的权值之和 $P_u \ge a_u$ 。
下层约束 (Descendants Condition)：其所有严格子孙结点的权值之和 $S_u \le a_u$ 。

关键性质观察：

上层约束的静态性：删除以 $v$ 为根的子树，只会移除树中的结点，而不会改变剩余结点在原树中的祖先关系及祖先的权值。因此，如果一个结点在原树中不满足上层约束，那么无论如何删边，它永远不可能成为“支撑结点”。
下层约束的动态性：删除以 $v$ 为根的子树后，受影响的仅为 $v$ 的所有祖先。对于 $v$ 的某个祖先 $u$ ，其子孙结点的权值之和将减少 $TotalSum(v)$ （即 $v$ 及其子树所有结点的权值之和）。这种减少可能导致原本不满足下层约束的 $u$ 变得满足约束。
删边的代价：删除子树 $v$ 会导致该子树内原有的所有支撑结点消失。我们需要在“通过删边获得的祖先支撑结点”与“因删边丢失的子树支撑结点”之间寻找最优平衡。

二、基于路径维护的树上动态统计

为了在 $O(N \log N)$ 的复杂度内解决问题，我们采用基于路径维护的树上动态统计算法。

1. 预处理阶段

通过两次深度优先遍历（DFS）获取原树的全局状态：

$P_u$ ：从根到 $u$ 的父节点的权值路径和。
$S_u$ ：以 $u$ 为根的子树内除 $u$ 以外的结点权值和。
$TotalSum(u)$ ：以 $u$ 为根的完整子树权值和（ $S_u + a_u$ ）。
$InitialSupport$ 标记：若结点满足 $P_u \ge a_u$ 且 $S_u \le a_u$ ，则标记为初始支撑结点。
$PotentialSupport$ 标记：若结点满足 $P_u \ge a_u$ 但 $S_u > a_u$ ，则标记为潜在支撑结点。

2. 差分贡献计算

设 $Count_{initial}$ 为原树中支撑结点的总数。若选择删除以 $v$ 为根的子树，新的稳定值为： $Score(v) = Count_{initial} - Loss(v) + Gain(v)$ 其中：

$Loss(v)$ ：以 $v$ 为根的子树中初始支撑结点的数量。可通过 DFS 后序遍历在 $O(N)$ 内求出。
$Gain(v)$ ： $v$ 的祖先中，有多少潜在支撑结点 $u$ 在删除 $v$ 后满足： $S_u - TotalSum(v) \le a_u \implies S_u - a_u \le TotalSum(v)$

3. 树上路径查询优化

计算 $Gain(v)$ 本质上是一个路径统计问题：对于结点 $v$ ，统计其到根结点的路径上，有多少个 $u \in PotentialSupport$ 满足 $S_u - a_u \le TotalSum(v)$ 。

数据结构：使用离散化后的树状数组（Fenwick Tree）。
执行过程：在 DFS 过程中，进入结点 $u$ 时，若 $u$ 为潜在支撑结点，将值 $S_u - a_u$ 插入树状数组；查询树状数组中所有 $\le TotalSum(u)$ 的元素个数，即为 $Gain(u)$ ；递归结束后，将 $u$ 移出树状数组（回溯）。

4. 边界条件处理

根结点（Node 1）：根据题意，其上层权值和为 0。若 $a_1 > 0$ ，根结点永远不可能是支撑结点。
叶子结点：其下层权值和为 0。
不删边的情况：即 $MaxDiff$ 与 0 取最大值。

三、代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++) {
        int fa;
        cin >> fa;
        if (fa != 0)
            adj[fa].push_back(i);
    }

    vector<ll> sz(n + 1, 0);   // 子树权值之和 (包含自身)
    vector<ll> p_sum(n + 1, 0);      // 严格祖先权值之和

    vector<bool> is_support(n + 1, false);     // 初始是否为支撑结点
    vector<bool> can_be_support(n + 1, false); // 是否满足上层约束
    vector<int> loss_cnt(n + 1,
                         0);           // 子树内初始支撑结点的数量
    vector<int> gain_val(n + 1,
                         0);           // 删掉该子树后，路径上能增加的支撑结点数

    vector<ll> coords; // 存储离散化的值
    vector<int> bit;
    auto update = [&](int x, int val) {
        for (; x < bit.size(); x += x & -x) bit[x] += val;
    };
    auto query = [&](int x) {
        int res = 0;
        for (; x > 0; x -= x & -x) res += bit[x];
        return res;
    };
    auto get_pos = [&](ll x) {
        return lower_bound(coords.begin(), coords.end(), x) - coords.begin() + 1;
    };

    auto dfs1 = [&](auto&& self, int u, ll cur_ancestor_sum) -> void {
        p_sum[u] = cur_ancestor_sum;
        sz[u] = a[u - 1];

        for (int v : adj[u]) {
            self(self, v, cur_ancestor_sum + a[u - 1]);
            sz[u] += sz[v];
        }

        if (p_sum[u] >= a[u - 1]) {
            can_be_support[u] = true;
            if (sz[u] - a[u - 1] <= a[u - 1]) {
                is_support[u] = true;
            }
        }
    };
    dfs1(dfs1, 1, 0);

    for (int i = 1; i <= n; i++) {
        coords.push_back(sz[i]);
        if (can_be_support[i]) {
            coords.push_back(sz[i] - 2 * a[i - 1]);
        }
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    bit.assign(coords.size() + 1, 0);

    auto dfs2 = [&](auto&& self, int u) -> void {
        loss_cnt[u] = (is_support[u] ? 1 : 0);
        for (int v : adj[u]) {
            self(self, v);
            loss_cnt[u] += loss_cnt[v];
        }
    };
    dfs2(dfs2, 1);

    int max_diff = 0;
    auto dfs3 = [&](auto&& self, int u) -> void {
        // 1. 计算 Gain: 如果删除以 u 为根的子树，其祖先有多少个能变强
        // 查询条件：S_u - a_u <= total_sz[v]
        gain_val[u] = query(get_pos(sz[u]));

        max_diff = max(max_diff, gain_val[u] - loss_cnt[u]);

        // 2. 插入当前结点作为“祖先”供子孙查询
        // 注意：只有还没达标(初始不是支撑点)但有潜力(满足上层约束)的点才贡献 Gain
        bool added = false;
        if (can_be_support[u] && !is_support[u]) {
            update(get_pos(sz[u] - 2 * a[u - 1]), 1);
            added = true;
        }

        for (int v : adj[u]) {
            self(self, v);
        }

        // 3. 回溯，撤销对树状数组的影响
        if (added) {
            update(get_pos(sz[u] - 2 * a[u - 1]), -1);
        }
    };
    dfs3(dfs3, 1);

    int initial_cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (is_support[i])
            initial_cnt++;
    }

    cout << initial_cnt + max_diff << endl;
}

四、复杂度分析

1. 时间复杂度： $O(N \log N)$

树的遍历（三次 DFS）均为 $O(N)$ 。
离散化涉及排序，复杂度为 $O(N \log N)$ 。
树状数组的操作：每个结点进出树状数组各一次，查询一次。在 $N$ 个结点的树上，单次操作 $O(\log N)$ ，总计 $O(N \log N)$ 。
总复杂度： $O(N \log N)$ 。

2. 空间复杂度： $O(N)$

存储树结构需 $O(N)$ 。
各类统计数组（ $P_i, S_i, Loss_i$ 等）及离散化数组需 $O(N)$ 。
树状数组空间为 $O(N)$ 。
递归栈空间在最坏情况下（链状树）为 $O(N)$ 。

题解 | #最大稳定数值#

一、 问题分析

二、 基于路径维护的树上动态统计