打卡信奥刷题（3290）用C++实现信奥题 P8966 觅光 | Searching for Hope (easy ver.)

P8966 觅光 | Searching for Hope (easy ver.)

题目背景

这是本题的简单版本。两个版本在100 % \bm{100 \%}100%数据范围的唯一区别是关于n \bm{n}n的限制。此版本中n ≤ 1000 \bm{n \le 1000}n≤1000。

有梦中所向往的地方，也有现实中可望不可触及的远方。

我们正等待无数次的希望，新的纪元，生命不曾奏响终章。

顷刻间颠覆中的一切，天空坠落到海底，死死卡住呼吸者的全部。羽翼裹满刺骨的海水，悲伤到从此遗忘呼吸的意义。

明明与空气只隔着毫厘，却不想再尝试去呼吸。我开始明白，悲伤到了极点，也许不会流泪

神明借着生的名义，捏造出灰暗的真理。

泪水模糊眼眶，身躯坠进天空，泛白的天光，不得已照亮这一日的希望。

题目描述

现在有一棵n nn个节点的有根二叉树。

凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带1 11单位正电荷或带1 11单位负电荷。

树上每一个点有容量，第i ii个点可以容纳c i c_ici​个球。初始每一个点容纳的球数为0 00。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。

每一次一个球下落到一个点时：

• 如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数+ 1 +1+1；
• 如果该点恰有一个孩子节点未充满，则向那个孩子下落；
• 如果有2 22个孩子节点均未充满：
  • 如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落；
  • 如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；
  • 如果左侧子树中所有球的电荷代数和等于右侧子树所有球的电荷代数和，则由神明决定向哪个方向下落。

其中，电荷代数和指的是正电荷的数量减去负电荷的数量。

在游戏开始前，双方约定目标点u uu。在一个回合中，凡人选择这次投下的球的电性，神明按上述规则控制球的下落过程。当u uu被充满时，游戏结束。

凡人希望游戏回合数尽量少，神明希望游戏回合数尽量多。假设双方足够聪明。

对所有：1 ≤ u ≤ n 1\leq u\leq n1≤u≤n，求游戏轮数r u r_uru​。

输入格式

第一行，一个正整数n nn。

第二行，n − 1 n-1n−1个整数f 2 , f 3 , … , f n f_2, f_3, \ldots, f_nf2​,f3​,…,fn​，其中f i f_ifi​代表i ii的父亲的编号。

第三行，n nn个整数c 1 , c 2 , … , c n c_1, c_2, \ldots, c_nc1​,c2​,…,cn​。

输出格式

输出一行，n nn个整数r 1 , r 2 , … , r n r_1, r_2, \ldots, r_nr1​,r2​,…,rn​。

输入输出样例 #1

输入 #1

5 1 1 2 2 1 1 1 1 1

输出 #1

5 4 2 3 3

说明/提示

【数据范围】

本题采用捆绑测试。

• 特殊性质 A：树退化成一条以1 11为一端的链。
• 特殊性质 B：c i = 1 c_i = 1ci​=1。

对于100 % 100\%100%的数据，2 ≤ n ≤ 1000 2 \le n \le 10002≤n≤1000，满足树是以1 11为根的二叉树，1 ≤ f i < i 1 \le f_i < i1≤fi​<i，1 ≤ c i ≤ 10 12 1 \le c_i \le {10}^{12}1≤ci​≤1012。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;main(){ios::sync_with_stdio(false);intn;cin>>n;vector<int>p(n,-1),c(n),s(n);vector<array<int,2>>k(n,{-1,-1});for(inti=1;i<n;i++){intx;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=[&](intu){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(inti=0;i<n;i++){intx=i,c=s[i];while(~p[x]){intb=(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;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容