题解 | 最大稳定数值

总结：三个dfs搜索，一个离散化处理，一个权值树状数组即可解决此问题

#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define all(a) a.begin(),a.end()
using namespace std ;
inline int lowbit(int x){return x & (~x + 1);}
struct ss
{
    vi t ; 
    ss () {}
    ss(int n) : t(n + 1) {}
    void add(int pos , int x)
    {
        for(int i = pos ; i < t.size() ; i += lowbit(i))
        {
            t[i] += x ; 
        }
    }
    int ask(int pos)
    {
        int sum = 0 ; 
        for(int i = pos ; i ; i -= lowbit(i))
        {
            sum += t[i] ;
        }
        return sum ; 
    }
}; 
signed main()
{
    int n ; cin >> n ; 
    vi a(n + 1) ; 
    for(int i = 1 ; i <= n ; i++)cin >> a[i] ; 
    vii g(n + 1) ; 
    for(int i = 1 ; i <= n ; i++)
    {
        int x ; cin >> x ; 
        if(x != 0)g[x].pb(i) ; 
    }
    vi base(n + 1 , 0) ; 
    vi mx(n + 1 , 0) ; 
    vi mi(n + 1 , 0) ; 
    vi num(n + 1 , 0) ; 
    auto dfs1 = [&](auto &&dfs1 , int u)->void{ 
        for(int v : g[u])
        {
            mx[v] = mx[u] + a[u] ; 
            dfs1(dfs1 , v) ; 
            mi[u] += (mi[v] + a[v]) ; 
        }
        base[u] = mi[u] + a[u] ;
    };
    auto dfs2 = [&](auto &&dfs2 , int u)->void{
        int sum = (mx[u] >= a[u] && mi[u] <= a[u]) ; 
        for(int v : g[u])
        {
            dfs2(dfs2 , v) ; 
            sum += num[v] ; 
        }
        num[u] = sum ;  
    };
    dfs1(dfs1 , 1) ; 
    dfs2(dfs2 , 1) ; 
    vi card ;
    for(int i = 1 ; i <= n ; i++)
    {
        if(mx[i] >= a[i] && mi[i] > a[i])
        card.pb(mi[i] - a[i]) ; 
        card.pb(base[i]) ; 
    }
    sort(all(card)) ; 
    card.erase(unique(all(card)) , card.end()) ; 
    ss tree(card.size()) ; 
    auto pos1 = [&](int x)->int{
      return lower_bound(all(card) , x) - card.begin() + 1 ;   
    } ; 
    vi go(n + 1 , 0) ; 
    auto dfs3 = [&](auto &&dfs3 , int u)->void{
        bool ok = false ;
        int it ; 
        if(mx[u] >= a[u] && mi[u] > a[u])
        {
            it = pos1(mi[u] - a[u]) ;
            tree.add(it , 1) ; 
            ok = true ; 
        }  
        for(int j : g[u])
        {
            int tar = upper_bound(all(card) , base[j]) - card.begin() ; 
            go[j] = tree.ask(tar) ; 
            dfs3(dfs3 , j) ;   
        }
        if(ok)
        {
            tree.add(it , -1) ; 
        }
    } ; 
    dfs3(dfs3 , 1) ; 
    int ans = num[1] ; 
    for(int i = 2 ; i <= n ; i++)
    {
        ans = max(ans , num[1] - num[i] + go[i]) ; 
    }
    cout << ans << endl ; 
    return 0 ; 
}