[codeforces round 800 D question fake plastic trees] greedy on the tree

Topic link

The question ：

Give you a tree , There is... In the tree n Nodes , The root node of the tree is 1, At first, the weight of each node in the tree is 0, Now there's an operation , Select a node , Make the weight of all nodes on the path from the root node to this node increase , The increasing range shows a non decreasing trend from the root node to this node , The weight of each node has a range , Give in the title input , Now I ask you how many such operations you need at least to make the weight of each node within its own range .

analysis ：

There is only one chance for a leaf node to be updated , When selecting leaf nodes , Then according to the greedy thought , First, update all leaf nodes to the maximum range , Why update to the maximum value here ？ Because if it's big , Its parent nodes will have more space , So we can start with leaf nodes , The white weight of each node is the sum of the increased weights of all its child nodes , If the weight of this white whore can be within the range, there is no need to do it again , This is based on greedy thinking , If the weight of white whores cannot meet the minimum value of the weight range of this node, then perform this operation on this point , Then you can use it again dfs To realize this idea , Now look at the code .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010,M = N+N;
int h[N],e[M],ne[M],idx;
int ans,n;
int l[N],r[N];
void add(int a,int b){
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u,int fa){
    
    int sum = 0;
    for(int i=h[u];i!=-1;i=ne[i]){
    
        int j = e[i];
        if(j == fa) continue;
        sum += dfs(j,u);
    }
    if(sum < l[u]){
    
        ans++;
        return r[u];
    }
    return min(sum,r[u]);
}
void solve(){
    
    ans = 0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
    
        h[i] = -1;
    }
    for(int i=2;i<=n;i++){
    
        int x;
        scanf("%lld",&x);
        add(i,x);
        add(x,i);
    }
    for(int i=1;i<=n;i++) scanf("%lld%lld",&l[i],&r[i]);
    dfs(1,0);
    cout<<ans<<endl;
}
signed main(){
    
    int _;
    scanf("%lld",&_);
    while(_--) solve();
    return 0;
}