纯粹是自己太唐导致的
我们发现其实这两种操作是独立的，并不需要考虑操作的相对顺序。
这时候就有两种解决顺序：
-
先子树加再链减
-
先链减再子树加
由于我一开始看错题了，所以我选了第一种思路，然后就爆炸了。
所以我们选第二种，钦定 \(d_x = a_{fa_x} - a_x\)，那么最后子树加的时候要保证的就是 \(d_x \ge 0\) 且 \(a^{'}_1 \le 0\)
我们考虑维护一个 \(g_x\) 表示 \(x\) 节点最多能被减多少次，然后我们就二分找到最多能减的次数即可。
具体来说就是考虑减 \(mid\) 次，其中 \(v\) 最多只能被减 \(g_v\) 次。
我们每操作一次，除了选的减的那个值之外其他的的 \(d_v\) 都会减 \(1\)。
所以再转换一下就变成了所有 \(d_v\) 都被减了 \(mid\) 次，你每次操作选择一个 \(d\) 加 \(1\)，使得 \(\forall_v,d_v \ge 0\)，且对于每个 \(v\) 最多操作 \(g_v\) 次。
这样就可以二分了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e13,N=1e5+5;
int C;
int T;
int n,a[N],fa[N];
vector<int> ed[N];
int g[N];
inline bool chk(int x,int val){
int sum=0;
for(auto v:ed[x]){
int num=a[x]-a[v]-val;
if(num>=0) continue;
if(g[v]<-num) return 0;
sum-=num;
}
return sum<=val;
}
inline void dfs(int x){
if(ed[x].empty()){g[x]=inf; return ;}
int l=0,r=0;
for(auto v:ed[x]) dfs(v),r+=g[v];
while(l<=r){
int mid=(l+r)>>1;
if(chk(x,mid)) g[x]=mid,l=mid+1;
else r=mid-1;
}
}
inline void solve(){
n=read();
for(int i=1;i<=n;i++) ed[i].clear();
for(int i=2;i<=n;i++) fa[i]=read(),ed[fa[i]].push_back(i);
for(int i=1;i<=n;i++) a[i]=read();
for(int i=2;i<=n;i++) if(a[fa[i]]<a[i]){puts("Shuiniao"); return ;}
dfs(1);
if(g[1]>=a[1]){puts("Huoyu"); return ;}
puts("Shuiniao");
}
signed main(){
// freopen("water.in","r",stdin);
// freopen("water.out","w",stdout);
C=read();
T=read();
while(T--) solve();
}