题解：CF1693B Fake Plastic Trees

CF1693B Fake Plastic Trees 题解

首先，对于一条路径，从根走到叶子节点明显更优（对于使操作次数更少来说）。
对于叶子节点 $v$ ， $l_v \leq a_v \leq r_v$ ，我们使对应的 $c_v = r_v$ 肯定是不劣的。
对于 $v$ 的父节点 $u$ （或任意非叶子节点）， $v$ 的贡献也一定会累加到 $u$ （因为到 $v$ 必须经过 $u$ ），则有 $\max \sum {c_u} \le \sum_{v \in son_u}^{v} \max \sum c_v$
我们可以设 $\sum_{v \in son_u} \max \sum c_v$ 为 $sum$ ，所以可以进行分类讨论：

对于 $sum<l_u$ ，可以把 $u$ 当作叶子节点再进行一次操作，使 $a_u=r_u$ 。
对于 $sum \in [ l_u,r_u ]$ ，直接返回。
对于 $sum > r_u$ ，修改 $a_i$ 。使 $au=r_u$ 后返回。

最后 dfs，递归解决 QwQ。

code

CPP

#include<bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
il ll read(){
	ll x=0;bool f=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return f?-x:x;
}
il void write(ll x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10|48);
}
const int N=2e5+5;
vector<int> g[N];
int l[N],r[N];
ll ans=0;
il ll dfs(int u){
	if(g[u].empty()) {++ans;return r[u];}
	ll sum=0;
	for(int v:g[u]) sum+=dfs(v);
	if(sum<l[u]) {++ans;return r[u];}
	return min(sum,(ll)r[u]);
}
il void solve(){
	int n=read();ans=0;
	for(int i=1;i<=n;++i) g[i].clear();
	for(int i=2,x;i<=n;++i) cin>>x,g[x].push_back(i);
	for(int i=1;i<=n;++i) cin>>l[i]>>r[i];
	dfs(1);
	write(ans);putchar('\n');
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}

完结撒花。

题解：CF1693B Fake Plastic Trees

文章操作

CF1693B Fake Plastic Trees 题解

相关推荐

评论

题解：CF1693B Fake Plastic Trees