P11189 「KDOI-10」水杯降温 题解

· · 题解

题目传送门

好题，但是赛时 inf 开太大痛失 56pts。

\tt{Sol.}

发现两种操作并不互相影响，考虑先做吹风操作，再做加热操作。

设第 i 个点初始水温为 t_i，所有吹风操作结束后第 i 个点的水温为 h_i。

那么原问题有解的充要条件是：h_{fa_i}\ge h_i 且 h_1\le 0。

证明显然。可以通过若干次加热操作将所有点的温度加热到 h_1，然后再在节点 1 上做加热操作即可使所有点温度升至 0。

不难发现，不管进行位于哪个叶子节点上的吹风操作，根节点的 h_1 一定会减少 1。所以条件 h_1\le 0 等价于要操作至少 t_1 次吹风操作。

现在来考虑吹风操作怎么做。

设 f_i 表示只对第 i 个点的子树内的叶子节点进行操作，且子树内除 i 节点外均满足 h_{fa_i}\ge h_i，的最多吹风操作使用次数。由定义得 h_i=t_i-f_i。

最好情况下 f_i=\sum_{v\in son_i} f_v，但有可能各个子树取最优会导致 h_i<h_v，不满足状态定义，所以对于一些 f_v 我们要适当“放弃”一部分。

设最终使 f_i 最大时，第 v 个点的子树内选取了 g_v\in[0,f_v] 次吹风操作。

那么有 t_i-\sum_{v\in son_i} g_v\ge \max_{v\in son_i}\{t_v-g_v\}，对于着上文 h_{fa_i}\ge h_i。

此时 f_i=\sum_{v\in son_i} g_v，观察到可行的 f_i 的选取是单调的。证明若 f_i 可行，(f_i-1) 也可行即可，非常好证。

然后二分答案 f_i。

总时间复杂度 O(n\log n)。

\tt{Code.}

#include <bits/stdc++.h>
#define fin(str) freopen(str,"r",stdin)
#define fout(str) freopen(str,"w",stdout)
#define ll long long
#define NO return (void)printf("Shuiniao\n")
#define YES return (void)printf("Huoyu\n")
using namespace std;

const int maxn=2e5+5;
const ll inf=1e12;//qwqwqwqwqwq

int type,T;

int n,fa[maxn];
vector <int> G[maxn];

ll a[maxn],f[maxn];

int flag_imp;

inline void DP(int x){
    if (flag_imp) return ;
    if (!G[x].size()){
        f[x]=inf;
        return ;
    }
    for (int i=0;i<G[x].size();i++){
        int v=G[x][i];
        DP(v);
        f[x]+=f[v];
    }

    ll l=0,r=f[x];
    while (l<=r){
        ll mid=(l+r)>>1;
        int flag=true;
        ll sum=0;
        for (int i=0;i<G[x].size();i++){
            int v=G[x][i];
            if (a[v]-f[v]>a[x]-mid){
                flag=false;
                break;
            }
            sum+=max(0ll,a[v]-(a[x]-mid));
        }
        if (flag && sum<=mid) l=mid+1;
        else r=mid-1;
    }

    f[x]=r;
    if (f[x]<0) flag_imp=true;
}

inline void solve(){
    scanf("%d",&n);

    for (int i=1;i<=n;i++) G[i].clear();
    for (int i=2;i<=n;i++){
        scanf("%d",&fa[i]);
        G[fa[i]].push_back(i);
    }
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (int i=2;i<=n;i++){
        if (a[fa[i]]<a[i]) NO;
    }

    for (int i=1;i<=n;i++) f[i]=0;
    flag_imp=false;
    DP(1);

    if (flag_imp) NO;
    if (f[1]<a[1]) NO;
    YES;
}

int main(){
//  fin("water7.in");
//  fout("water.out");
    scanf("%d%d",&type,&T);
    while (T--) solve();
    return 0;
}