题解 | 最大稳定数值

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 1e5 + 5;

int n;
int a[N];
LL prefix[N];
bool is_support[N], can_be_support[N];
LL siz[N];
int num[N];

vector<int> e[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i = 1; i <= n ;i++) cin>>a[i];
    for(int i = 1; i <= n; i++){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    auto dfs1 = [&](auto && self, int x, int fa) -> void {
        prefix[x] = prefix[fa] + a[x];
        siz[x] = a[x];
        for(int v:e[x]){
            if(v == fa) continue;
            self(self,v,x);
            siz[x] += siz[v];
            num[x] += num[v];
        }
        if(prefix[x] - a[x] >= a[x]){
            if(siz[x] - a[x] <= a[x]) {
                is_support[x] = true;
                num[x] ++;
            }
            else can_be_support[x] = true;
        }
    };
    dfs1(dfs1,1,0);
    vector<LL> b;
    for(int i = 1; i <= n; i++){
        b.push_back(siz[i]);
        if(can_be_support[i]) b.push_back(siz[i] - 2*a[i]);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    auto get = [&](LL x) {
        return lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
    };
    vector<int> tr(b.size() + 1);
    auto lowbit = [&](int x) {
        return x & -x;
    };
    auto update = [&](int x, int y) -> void {
        for(; x < b.size(); x += lowbit(x)) tr[x] += y;
    };
    auto query = [&](int x) {
        int res = 0;
        for(; x > 0; x -= lowbit(x)) res += tr[x];
        return res;
    };
    int ans = num[1];
    auto dfs2 = [&](auto && self, int x, int fa) -> void{
        ans = max(ans, num[1] - num[x] + query(get(siz[x])));
        if(can_be_support[x]) update(get(siz[x] - 2 * a[x]), 1);
        for(int v:e[x]){
            if(v == fa) continue;
            self(self, v, x);
        }
        if(can_be_support[x]) update(get(siz[x] - 2 * a[x]), -1);
    };
    dfs2(dfs2, 1, 0);
    cout<<ans;
    return 0;
}