题解：CF1693B Fake Plastic Trees

cogimyun · 2025-10-29 16:15:15 · 题解

我们首先考虑叶节点 u，我们必然要向 1 到 x 的链加上一个权值 c\in[l_u,r_u]，不难发现，由于对一个链加上的权值从根到叶节点满足 c_1\le c_2\le c_3\le ...\le c_k，那么 c 取最大值 r_u 自然不劣。接下来考虑非叶节点 u，我们发现所有操作中加到了 u 子节点 v\in Son_u 的操作必然会操作到 u 上面，那么对于 u 的最大加值 \max\sum c_u\le \sum\limits_{v\in Son_u}\max\sum c_v，我们不妨记这个最大加值为 add，则有如下几种情况：

于是我们就可以愉快地进行 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;
}