B. Fake Plastic Trees
看了第三个样例 发现一个节点可以由他的几个子节点一起构成
我们首先自下而上的看
肯定叶子节点越大越好 这样我们选择的空间就会越多
再者要是我们该节点的L还是小于我们叶子节点的sum 那我们不得不再加一次操作
而对于这次操作我们还是可以贪心的把他看成叶子节点
所以我们return的时侯显然有两种情况
第一种是叶节点sum够 return min(sum,r[u])
第二种是不够 直接ans++ return r[u]即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
vector<int>g[N];
int n,fa[N],ans,L[N],R[N];
int dfs(int u){
int res=0;
for(auto v:g[u]){
res+=dfs(v);
}
if(res<L[u])ans++,res=R[u];
return min(R[u],res);
}
void solve() {
cin>>n;
for(int i=1;i<=n;i++)g[i].clear();
for(int i=2;i<=n;i++){
cin>>fa[i];
g[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++){
cin>>L[i]>>R[i];
}
ans=0;
dfs(1);
cout<<ans<<endl;
}
signed main(){
fast
int t;t=1;cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:return,int,Codeforces,dfs,ans,const,800,节点,div1
From: https://www.cnblogs.com/ycllz/p/16773106.html