题解：CF1693B Fake Plastic Trees

我们首先考虑叶节点

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

，则有如下几种情况：

$add<l_u$ 那么我们必然需要向 $1$ 到 $u$ 的链进行一次操作，此时与在叶节点时同理，应该增加权值 $r_u-add$ 使得 $add$ 最大化为 $r_u$ 。
$add\in[l_u,r_u]$ 此时我们无需对此节点进行操作。
$add>r_u$ 那么我们对于节点 $u$ 的加值超过了上限，所以我们应该将 $add$ 下调为 $r_u$ 之后再上传至其父节点。

于是我们就可以愉快地进行 dfs 了。

CODE

CPP

#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;
}

题解：CF1693B Fake Plastic Trees

文章操作

CODE

相关推荐

评论

题解：CF1693B Fake Plastic Trees