Fake Plastic Trees

_QyGyQ_ · 2024-01-01 14:14:03 · 题解

思路

贪心，从叶子节点往上。对于当前节点，先记录自己儿子的贡献，如果贡献小于自己的左区间，那么就使用一次机会，将自己的权值直接顶到有区间，否则就将贡献与右区间取最小值。最后输出答案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
const int N=1e6+7;
int w[N],l[N],r[N];
vector<int>G[N];
int n;
int ans;
void dfs(int u){
    int cnt=0;
    for(int i=0;i<G[u].size();i++){
        dfs(G[u][i]);
        cnt+=w[G[u][i]];
    }
    if(cnt<l[u]){
        w[u]=r[u];
        ans++;
    }
    else{
        w[u]=min(r[u],cnt);
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=n;i++){
            G[i].clear();
        }
        cin>>n;
        ans=0;
        for(int i=2;i<=n;i++){
            int p;
            cin>>p;
            G[p].push_back(i);
        }
        for(int i=1;i<=n;i++){
            cin>>l[i]>>r[i];
        }
        dfs(1);
        cout<<ans<<"\n";
    }
    return 0;
}