题解：CF1693B Fake Plastic Trees

HNO_3 · 2025-11-05 21:27:54 · 题解

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，所以可以进行分类讨论：
  1. 对于 sum<l_u，可以把 u 当作叶子节点再进行一次操作，使 a_u=r_u 。
  2. 对于 sum \in [ l_u,r_u ]，直接返回。
  3. 对于 sum > r_u，修改 a_i。 使 au=r_u 后返回。
• 最后 dfs，递归解决 QwQ。 ::::success[code]

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

:::: 完结撒花。