[luogu P11189] 水杯降温

Cyan0826 / 2025-02-21 / 原文

~~纯粹是自己太唐导致的~~

我们发现其实这两种操作是独立的，并不需要考虑操作的相对顺序。

这时候就有两种解决顺序：

先子树加再链减
先链减再子树加

~~由于我一开始看错题了~~，所以我选了第一种思路，然后就爆炸了。

所以我们选第二种，钦定 $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();
}