我們首先考慮葉節(jié)點(diǎn) \(u\)，我們必然要向 1 到 \(x\) 的鏈加上一個權(quán)值 \(c\in[l_u,r_u]\)，不難發(fā)現(xiàn)，由于對一個鏈加上的權(quán)值從根到葉節(jié)點(diǎn)滿足 \(c_1\le c_2\le c_3\le ...\le c_k\)，那么 \(c\) 取最大值 \(r_u\) 自然不劣。接下來考慮非葉節(jié)點(diǎn) \(u\)，我們發(fā)現(xiàn)所有操作中加到了 \(u\) 子節(jié)點(diǎn) \(v\in Son_u\) 的操作必然會操作到 \(u\) 上面，那么對于 \(u\) 的最大加值 \(\max\sum c_u\le \sum\limits_{v\in Son_u}\max\sum c_v\)，我們不妨記這個最大加值為 \(add\)，則有如下幾種情況：

1. \(add<l_u\) 那么我們必然需要向 \(1\) 到 \(u\) 的鏈進(jìn)行一次操作，此時與在葉節(jié)點(diǎn)時同理，應(yīng)該增加權(quán)值 \(r_u-add\) 使得 \(add\) 最大化為 \(r_u\)。
2. \(add\in[l_u,r_u]\) 此時我們無需對此節(jié)點(diǎn)進(jìn)行操作。
3. \(add>r_u\) 那么我們對于節(jié)點(diǎn) \(u\) 的加值超過了上限，所以我們應(yīng)該將 \(add\) 下調(diào)為 \(r_u\) 之后再上傳至其父節(jié)點(diǎn)。

于是我們就可以愉快地進(jìn)行 dfs 了。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> e[200005];
int f[200005],n,ans,t;
struct node{
    int l,r;
}a[200005];
int  dfs(int x){
    if(e[x].empty()){ans++;return a[x].r;}
    int sum=0;
    for(auto i:e[x])sum+=dfs(i);
    if(sum<a[x].l){ans++;return a[x].r;}
    return min(sum,a[x].r);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        ans=0;
        cin>>n;
        for(int i=1;i<=n;i++)e[i].clear();
        for(int i=2;i<=n;i++){cin>>f[i];e[f[i]].push_back(i);}
        for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
        dfs(1);
        cout<<ans<<endl;
    }
    return 0;
}