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

Lavaloon · 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;
}

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