自动搬运

查看原文

来自洛谷，原作者为

	Lavaloon zzzzzzzzzzzz4

搬运于2025-08-24 23:05:06，当前版本为作者最后更新于2024-10-14 15:27:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Update on 2024.10.15：$anc_i$ 的定义并不完善，事实上应包含 $i$ 节点本身的贡献。在此感谢 @Fatalis 的指出！

Update on 2024.12.10：刚刚了解到使用 align* 而非 align 可以去除公式后的编号，为优化读者阅读体验故作出修改。辛苦管理员了！

Update on 2025.7.13：虽然笔者已经退役但是我咋刚刚注意到文章所有左右引号都用反了啊，在此改正。

---

很多人赛时考虑过“先做子树加操作，再去判定链减的合法性”的思路，但在中途改变了想法。故该题解旨在说明该思路的可行性。

做法可能相对复杂，但笔者相信其亦具有一定的参考性。

基本定义

下将“链减”操作称为 A 操作，“子树加”操作称为 B 操作。

下记 $\mathbb{LEAF}$ 为叶节点所组成的的集合，$e_i$ 为 $i$ 的子节点所组成的集合，$fa_i$ 为 $i$ 的父节点（即题目中的 $f_i$）。

记 $d_i$ 为 $i$ 的子节点所组成的集合大小，即子节点个数。

确定大体思路

可以考虑先进行一种操作，再去判断：进行完这一种操作后的局面是否能使用另一种操作，来使局面变得合法。

讨论两种思路：

• 思路一：若一个局面在只使用 A 操作下可以变得合法，则需要满足：
  • 条件一：$\forall i,a_i\ge 0$;
  • 条件二：$\forall i\notin \mathbb{LEAF},a_i=\sum_{j\in e_i} a_j$.
• 思路二：若一个局面在只使用 B 操作下可以变得合法，则需要满足：
  • 条件一：$\forall i,a_i\le 0$;
  • 条件二：$\forall i\ne 1,a_i\le a_{fa_i}$.

注意到题目给出的 B 性质恰为：$a_i\le \left(\sum_{{j\in e_i}}a_j\right)+5$，于是我们对思路一进行考虑！！！

考察判定条件

下文的所有内容将围绕思路一展开。

考察条件二的等式，令 $b_i=a_i-\sum_{j\in e_i} a_j$，答案是否存在的判定即转化为：对 $\forall i\notin \mathbb{LEAF},b_i=0$ 可行性的判定。

特别地，将 $b_i$ 对于 $i\in \mathbb{LEAF}$ 定义为 $a_i$。

考察一次 B 操作对 $b$ 数组的影响。

若对 $u$ 子树执行一次 B 操作，那么：

• 对于 $u$ 子树内任意一非叶节点 $i$，$b_i\leftarrow b_i-d_i+1$;
• 对于 $u$ 的父节点 $p$，$b_p\leftarrow b_p-1$.

每一次操作后 $b_i$ 不增。

因此对于原局面的一个非叶结点 $i$，若有 $b_i<0$，那么一定无解。提前判掉。

优化判定形式

当时我接下来就没啥思路了，于是我选择将每个点执行了几次 B 操作设出来：

设对 $i$ 子树执行了 B 操作的次数为 $c_i$。

下令 $anc_i$ 表示 $i$ 节点及其祖先所构成的集合。

那么在执行完所有 B 操作后，$b_i$ 的值应当为 $0$，这给出：

$$b_i=\sum_{j\in e_i} c_j+(d_i-1)\sum_{j\in anc_i} c_j $$

这个式子的结构相当令人恼火。

首先，其具有非常丑陋的后效性——无论是考虑从上到下确定 $c_i$，还是从下到上确定 $c_i$，都无法简单建立递推关系。

其次，该式中 $c_i$ 的取值和 $i$ 的所有祖先都有关，而这种结构着实难以处理。

这启发我们定义：

$$f_i=\sum_{j\in anc_i} c_j$$

注意：由 $f_i$ 的定义，我们需要保证 $f_i\ge f_{fa_i}$.

将 $c_i$ 用 $f_i-f_{fa_i}$ 替换，得出：

$$\begin{align*} b_i&=\sum_{j\in e_i} (f_j-f_i)+(d_i-1)f_i \\ &=\sum_{j\in e_i} f_j-f_i \end{align*} $$

这个式子的结构非常优雅且具有高贵的无后效性！现在我们可以考虑自底向上确定 $f_i$ 的思路了。

设计判定信息

下文遵循自底向上考虑的逻辑顺序展开。

首先是考虑所有叶子：假如 $b_i<0$，那么 $f_i$ 至少要是 $-b_i$，否则 $f_i$ 的下界是 $0$（这其实是思路一的条件一）。

对于一个子节点全是叶子的节点 $u$，若 $f_u=k$ 是可行的，那么需要满足以下条件：

$$\sum_{v\in e_u} \max(-b_v,k)\le b_u+k$$

左边是每个叶子节点 $f_v$ 取值的下界之和，其应当小于等于 $b_u+k$。因为要是这个成立的话，只需要把一些 $f_v$ 取大一点，就可以构造出 $b_u=\sum_{v\in e_u} f_v-k$ 了。

这启示我们对于每个 $u$ 维护 $f_u$ 的下界。不妨记之为 $\ell_u$.

假如我们已经确定了 $\ell_u$，那么 $k$ 可以取到的值应呈现如何的性质？

可以考虑暴力从 $\ell_u$ 开始枚举，一个个 Check 每个值（不妨称为 $t$）作为 $k$ 是否合法。这个值增大 $1$ 的过程中，上式会发生如下变化：

• 对于右边：

  • 稳定增大 $1$.

• 对于左边：

  • 一开始可能会比任何一个 $-b_v$ 都小，每次增大 $0$；
  • 随着 $t$ 的增大，可能会恰好超过其中一个 $-b_v$，每次增大 $1$；
  • 又随着 $t$ 的增大，可能会恰好超过其中两个 $-b_v$，每次增大 $2$；
  • 以此类推。

那么 $b_u+t-\sum_{v\in e_u} \max(-b_v,t)$ 呈先增后减，这给出：

$k$ 可以取到的值是一段区间。

这启示我们对于每个 $u$ 维护 $f_u$ 的上界。不妨记之为 $r_u$.

这同时启示我们使用二分即可轻松求得 $r_u$，只需要把上面 $f_u=k$ 可行的条件抄下来 check 就行了。

回过头来思考如何求解 $\ell_u$。

• 首先，在“左边每次增大 $0$ ”终止的那个时刻（上图点 $\text{B}$），$b_u+t-\sum_{v\in e_u} \max(-b_v,t)$ 达到巅峰。左端点一定在此位置或其之前。
• 其次，假如在点 $\small\mathrm{B}$ 之前，那么每往前一步，这个值就减 $1$。然而这个值要始终大于等于 $0$，那么可行的左端点就是容易求得的。

于是我们解决了子节点都是叶子的情况。

对于子节点不全是叶子的情况，处理思路与之类似。具体来说：

若 $f_u=k$ 是可行的，那么需要满足以下条件：

$$\begin{align*} \left\{\begin{matrix} \sum_{v\in e_u} \max(\ell_v,k)&\le b_u+k \\ \sum_{v\in e_u} r_v&\ge b_u+k \end{matrix}\right. \end{align*} $$

解释一下：

• 上面那个式子和之前的那个类似，即每个子节点 $f_v$ 取值的下界之和，应当小于等于 $b_u+k$.

• 下面那个式子是说，上界不能小于 $b_u+k$。这样才能确保 $b_u+k$ 是取得到的（为什么在子节点全是叶子的情况中没有这一条？因为叶子节点 $i$ 的 $g_i$ 可以被认为是 $+\infty$，该式自然满足）。

可以使用与上一种情况类似的思路求解 $\ell_u$ 和 $r_u$。

至此我们解决了整个问题。

程序流程

• 首先求解 $b_i$。若存在非叶结点 $b_i<0$ 则返回无解并退出。

• 接下来递归求解 $f_i$：

  • 对叶子节点，定下界 $\ell_i=\max(0,-b_i)$，上界 $r_i=+\infty$.
  • 对非叶节点，容易计算 $\ell_i$ 并通过二分确定 $r_i$。若不存在合法的 $r_i$ 则返回无解并退出。
    • 二分的上下界存在细节：前文那个大括号下面的式子不能忽略。

• 返回有解，退出程序。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Mx=100005,p=998244353;
int read(){
	char ch=getchar();
	int Alice=0,Aya=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') Aya=-Aya;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		Alice=(Alice<<3)+(Alice<<1)+(ch^48),ch=getchar();
	return (Aya==1?Alice:-Alice);
}
int n;
int fa[Mx];
int a[Mx],b[Mx];
int deg[Mx];
int l[Mx],r[Mx];
vector<int>e[Mx];
void Solve(){
	n=read();
	for(int i=1;i<=n;i++) deg[i]=0,l[i]=0,r[i]=1e13,e[i].clear();
	for(int i=2;i<=n;i++) fa[i]=read(),deg[fa[i]]++,e[fa[i]].push_back(i);
	for(int i=1;i<=n;i++) a[i]=b[i]=read();
	for(int i=2;i<=n;i++) b[fa[i]]-=a[i];//计算 b[i]
	for(int i=1;i<=n;i++){
		if(deg[i]&&b[i]<0){//判无解
			puts("Shuiniao");
			return;
		}
	}
	for(int i=1;i<=n;i++) if(deg[i]==0&&b[i]<0) l[i]=-b[i];
	for(int i=n;i>=1;i--){
		if(deg[i]==0) continue;
		int L=1e13,R=1e13,ok=-1;
		for(int v:e[i]) L=min(L,l[v]);
		for(int v:e[i]) R=min(R,r[v]);
		int sf=0,sg=0;
		for(int v:e[i]) sf+=l[v];
		for(int v:e[i]) sg+=r[v];
		if(sg<b[i]){
			puts("Shuiniao");
			return;
		}
		L=min(L,sg-b[i]),R=min(R,sg-b[i]);//注意二分的上下界
		l[i]=min(L,max(0ll,sf-b[i]));//计算下界
		while(L<=R){
			int mid=((L+R)>>1);
			int w=0;
			for(int v:e[i]) w+=max(mid,l[v]);
			w-=mid;
			if(w<=b[i]) L=mid+1,ok=mid;
			else R=mid-1;
		}
		if(ok==-1){//判无解
			puts("Shuiniao");
			return;
		}
		r[i]=ok;//二分上界
	}
	puts("Huoyu");
}
signed main(){
	read();
	int T=read();
	for(int i=1;i<=T;i++) Solve();
	return 0;
}