个人错误汇总
查看原帖
个人错误汇总
360025
zzyaba楼主2024/10/16 19:02
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fll
int t,n,l,r,s,mid,cnt,f[100001],a[100001],dp[100001];
vector<int>g[100001];
void dfs1(int cur){
    for(auto&i:g[cur]){
        dfs1(i);
        a[i]-=a[cur];
    }
}
signed main(){
    freopen("water7.in","r",stdin);
    freopen("water7.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>t;
    while(t--){
        if(0){
            nextloop:
                continue;
        }
        cin>>n;
        for(int i=1;i<=n;i++){
            g[i].clear();
        }
        for(int i=2;i<=n;i++){
            cin>>f[i];
            g[f[i]].push_back(i);
        }
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        dfs1(1);
        for(int i=2;i<=n;i++){
            if(a[i]>0){
                cout<<"Shuiniao\n";
                goto nextloop;
            }
        }
        for(int k=n;k>=1;k--){//问题1:使用dfs会爆栈(样例5)
            if(g[k].empty()){
                dp[k]=inf;
                continue;
            }
            l=0;
            r=0;
            for(auto&i:g[k]){
                r=min(r+dp[i],inf);//问题2:ll处理
            }
            for(auto&i:g[k]){
                r=min(r,dp[i]-a[i]);//问题3:每棵子树的处理
            }
            while(l<r){
                mid=(l+r+1)/2;
                cnt=0;
                for(auto&i:g[k]){
                    cnt=min(cnt+max(0ll,mid+a[i]),inf);//问题2:ll处理&问题4:负数处理
                }
                if(cnt>mid){
                    r=mid-1;
                }else{
                    l=mid;
                }
            }
            dp[k]=l;
        }
        if(dp[1]>=a[1]){
            cout<<"Huoyu\n";
        }else{
            cout<<"Shuiniao\n";
        }
    }
}
2024/10/16 19:02
加载中...