P8966 题解（2023 激励计划评分 8）

FFTotoro · 2023-12-11 21:55:35 · 题解

前言

一年前赛时过的题，来补个题解。

解法

显然凡人只能投一种电荷（不妨设为正电荷），否则必然不优，原因显然。

因为神明要让游戏轮数变多，所以如果它可以决策，都得往与目标点所在方向的相反的方向扔。而又因为要左右子树电荷数平衡，所以先得在另一棵子树填上与目标所在子树的答案相等数量的电荷，注意另一棵子树的子树和不一定大于目标所在子树的答案，此时把另一棵子树填满即可。

枚举每一种目标结点，不断往上找父亲并更新答案。具体地，令另外一棵子树大小为 S，当前答案为 c，则 c\leftarrow c+\min\{c,S\}。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> p(n,-1),c(n),s(n);
  vector<array<int,2> > k(n,{-1,-1});
  for(int i=1;i<n;i++){
    int x; cin>>x; p[i]=--x;
    (~k[x][0]?k[x][1]:k[x][0])=i;
  } // 建树
  for(auto &i:c)cin>>i;
  function<void(int)> dfs=[&](int u){
    if(~k[u][0])dfs(k[u][0]),s[u]+=s[k[u][0]];
    if(~k[u][1])dfs(k[u][1]),s[u]+=s[k[u][1]];
  }; // 预处理子树和
  s=c,dfs(0);
  for(int i=0;i<n;i++){
    int x=i,c=s[i];
    while(~p[x]){
      int b=(x==k[p[x]][0]?k[p[x]][1]:k[p[x]][0]);
      c+=min(c,~b?s[b]:0),x=p[x];
    } // 暴力找父亲，更新答案
    cout<<c<<' ';
  }
  cout<<endl;
  return 0;
}