The problem can be found here

My Thought Process

This was a quite straightforward problem.

We should definitely look at the leaves first since it isn’t affected by any other operations. It is optimal to always let $c_k$ to be $r_k$ since the array is just non-decreasing and then we might be able to have a greater number for $c_{k-1}$.

Lets look at the nodes above the leaf. What happen if $c_k$ is greater than the its left interval? Well, great, that mean in one operation we can essentially get two nodes to be in the correct intervals. If not, we need to use another operation.

Also, if there are two leaves that shares a parent, then if we use two operations, one on each leaf (we need to because they are leaves and paths don’t cross two leaves), the parent can have a number between $0$ and the sum of both leave’s right interval bound.

So, if a the parent needs a number from $[5,7]$ and the leaves need numbers $[1,4]$ and $[1,3]$, we can just set the leaves to $4$ and $3$ and the parent can have its number increased by $4$ and $3$ for a total of $7$.

Implementation

My following implementation is very similar to the editorial’s.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

#define int long long
int n;
vector<pair<int, int>> v;
vector<vector<int>> g;
int ans = 0;

int dfs(int x, int p){
    int k = 0;

    for(int u : g[x]){
        if(u == p){continue;}
        k += dfs(u, x);
    }

    if(k < v[x].first){
        ans++;
        return v[x].second;
    }

    return min(k, v[x].second);
}
void solve() { 
    cin >> n;

    v = vector<pair<int, int>>(n);
    g = vector<vector<int>>(n);
    ans = 0;

    for(int i = 1; i < n; ++i){
        int x; cin >> x;
        x--;
        g[i].pb(x);
        g[x].pb(i);
    }

    for(int i = 0; i < n; ++i){
        int x, y; cin >> x >> y;
        v[i] = {x,y};
    }

    dfs(0, -1);

    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.