题解 | 最大稳定数值

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;

class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 2, 0) {} // 多开2防止越界
    
    void update(int idx, int delta) {
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    int query(int idx) {
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> father(n + 1);
    vector<vector<int>> children(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> father[i];
        if (i != 1) {
            children[father[i]].push_back(i);
        }
    }
    
    // 1. 后序计算sum_sub和down
    vector<ll> sum_sub(n + 1), down(n + 1);
    function<void(int)> dfs1 = [&](int u) {
        sum_sub[u] = a[u];
        for (int v : children[u]) {
            dfs1(v);
            sum_sub[u] += sum_sub[v];
        }
        down[u] = sum_sub[u] - a[u];
    };
    dfs1(1);
    
    // 2. 先序计算up
    vector<ll> up(n + 1, 0);
    function<void(int)> dfs2 = [&](int u) {
        for (int v : children[u]) {
            up[v] = up[u] + a[u];
            dfs2(v);
        }
    };
    dfs2(1);
    
    // 3. 计算is_support和sub_support
    vector<bool> is_support(n + 1);
    vector<int> sub_support(n + 1);
    function<void(int)> dfs3 = [&](int u) {
        is_support[u] = (up[u] >= a[u]) && (down[u] <= a[u]);
        sub_support[u] = is_support[u];
        for (int v : children[u]) {
            dfs3(v);
            sub_support[u] += sub_support[v];
        }
    };
    dfs3(1);
    int total = sub_support[1];
    
    // 4. 离散化所有需要的值（修正部分）
    vector<ll> all_values;
    for (int x = 1; x <= n; x++) {
        if (up[x] >= a[x] && down[x] > a[x]) {
            all_values.push_back(down[x] - a[x]); // 存down[x]-a[x]
        }
    }
    for (int v = 1; v <= n; v++) {
        all_values.push_back(sum_sub[v]); // 存sum_sub[v]
    }
    sort(all_values.begin(), all_values.end());
    all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
    
    auto get_id = [&](ll x) {
        return lower_bound(all_values.begin(), all_values.end(), x) - all_values.begin() + 1;
    };
    
    // 5. DFS计算delta数组（修正部分）
    FenwickTree ft(all_values.size());
    vector<int> delta(n + 1, 0);
    
    function<void(int)> dfs4 = [&](int u) {
        // 先算delta[u]（此时树状数组只有u的真祖先）
        ll K = sum_sub[u]; // 只需要sum_sub[u]
        int id = get_id(K);
        delta[u] = ft.query(id);
        
        // 再把u加入树状数组（供它的孩子使用）
        if (up[u] >= a[u] && down[u] > a[u]) {
            ft.update(get_id(down[u] - a[u]), 1); // 存down[u]-a[u]
        }
        
        // 递归访问孩子
        for (int v : children[u]) {
            dfs4(v);
        }
        
        // 回溯时删除u
        if (up[u] >= a[u] && down[u] > a[u]) {
            ft.update(get_id(down[u] - a[u]), -1);
        }
    };
    dfs4(1);
    
    // 6. 计算最大值
    int ans = total; // 不删除任何边的情况
    for (int v = 1; v <= n; v++) {
        ans = max(ans, total - sub_support[v] + delta[v]);
    }
    
    cout << ans << endl;
    return 0;
}