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

很精妙的一个树形 dp。

两个操作都影响很多点比较烦，我们尝试通过树上差分的方式使得其中一个操作只影响一个点。

如果我们想要使得修改子树的操作只影响一个点，则我们要将每一个节点的权值减去父亲节点的权值。但是此时修改链的操作会影响一条路径上每一个点的所有孩子，这个范围看起来非常难以处理。从而我们尝试使得修改链的操作只影响一个点，我们要将每一个点的权值减去自己的所有孩子的权值和。我们设 $u$ 节点的差分值为 $d_u$。

这样，一次链加只会影响链头的值，同时我们只能对叶子进行链加操作。同时我们不难发现，如果整个树可以变为全 $0$，则我们只考虑任意一个子树时，它仍然可以变为全 $0$。

这个性质启发我们使用树形 dp 解决这个问题。我们尝试设 $f_u=0/1$ 表示 $u$ 子树是否可以变为全 $0$，但是这样显然无法转移，因为 $u$ 的祖先进行的子树 $+1$ 操作会影响到 $u$ 的子树。于是我们设 $f_{u,i}=0/1$ 表示 $u$ 子树进行了恰好 $i$ 次全局 $+1$，是否可以变为全 $0$。当然这样复杂度太大了，但是我们先不管这个。

我们考虑如何转移。对于叶子 $u$，如果 $d_u\geq 0$，则进行任意次全局 $+1$ 都有解；如果 $d_u<0$，则必须至少进行 $-d_u$ 次全局 $+1$ 才有解。

对于非叶子节点 $u$，设它的孩子分别是 $v_1,v_2,\cdots,v_c$，我们假设节点 $u$ 被进行了 $x$ 次全局 $+1$ 操作：

• 此时，$d_u$ 减少了 $(c-1)x$。
• $u$ 的每一个孩子都被进行了 $x$ 次操作。
• 每次对一个孩子单独进行整体 $+1$ 时，我们会将根的差分值减少 $1$，我们需要将其减少至 $0$。由于我们已经限制了整体加的次数，其余操作均不会影响根的差分值。

从而 $f_{u,x}=1$ 的条件可以被转化为：

• $d_u-(c-1)x \geq 0$；
• $\exists w_1,w_2,\cdots,w_c$ 使得：
  • $w_1,w_2,\cdots,w_c>0$；
  • $w_1+w_2+\cdots+w_c=d_u-(c-1)x$；
  • $f_{v_1,x+w_1}=f_{v_2,x+w_2}=\cdots=f_{v_c,x+w_c}=1$。

这个转移看起来很难优化，但是我们模拟几组样例容易发现对于任意一个点，$f_u$ 为 $1$ 的位置一定构成一个区间。我们可以归纳证明这个形式。对于叶子，该结论显然是成立的。

对于任意非叶子节点 $u$，如果它的某一个孩子 $v$ 的 $f_v$ 值为 $1$ 的区间为空，则 $f_u$ 的值为 $1$ 的区间也为空。于是我们只考虑区间不为空的情况。我们设孩子 $v_1,v_2,\cdots,v_c$ 对应的区间分别是 $[l_1,r_1],[l_2,r_2],\cdots,[l_c,r_c]$。则我们的条件可以被写作：

• $x\leq \min r_i$；
• $d_u-(c-1)x\in \left[\sum_{i=1}^c\max\{0,l_c-x\}, \sum_{i=1}^c(r_c-x)\right]$。

对于第二个限制，我们进一步将其拆分：

• $d_u-(c-1)x\geq \sum_{i=1}^c\max\{0,l_c-x\}$；
  • 由于右侧是一个凸函数，所以这个限制一定是一个区间。
• $d_u-(c-1)x\leq \sum_{i=1}^c(r_c-x)$。
  • 这个不等式进一步化为 $x\leq \sum_{i=1}^cr_i-d_u$。

这样我们就说明了合法的 $x$ 一定构成一段区间。接下来的问题就是求出这段区间。此时不容易处理的只有 $d_u-(c-1)x\geq \sum_{i=1}^c\max\{0,l_c-x\}$ 这条限制。

注意到由于右侧关于 $x$ 的最小斜率是 $-c$，左侧的斜率是 $-(c-1)$，于于是如果区间不为空，则左端点一定 $\leq \min l_i$。于是这个限制对应的区间左端点就是 $L=\sum_{i=1}^cl_i-d_u$，同时如果 $L>\min l_i$，则无解。

求出 $L$ 后，该限制的区间右端点即可通过从 $L$ 开始二分求出。

最后只需判定根的区间是否为空即可。于是这题就做完了。复杂度 $O(n\log V)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector <int> g[N];
int n;
long long w[N], l[N], r[N];

inline void Read() {
    cin >> n;
    for (int i = 2;i <= n;i++) {
        int fa;
        cin >> fa;
        g[fa].push_back(i);
    }
    for (int i = 1;i <= n;i++) cin >> w[i];
}

inline void Dfs(int u) {
    if (g[u].size() == 0) {
        l[u] = max(0ll, -w[u]);
        r[u] = 1e13;
        return;
    }
    if (w[u] < 0) {
        l[u] = 0;
        r[u] = -1;
        return;
    }
    long long ml = 1e13, smr = 0;
    r[u] = 1e13;
    l[u] = 0;
    for (int v : g[u]) {
        Dfs(v);
        if (l[v] > r[v]) {
            l[u] = 0;
            r[u] = -1;
            return;
        }
        ml = min(ml, l[v]);
        l[u] += l[v];
        r[u] = min(r[u], r[v]);
        smr += r[v];
    }
    r[u] = min(r[u], smr - w[u]);
    if (g[u].size() > 1) r[u] = min(r[u], w[u] / ((long long)g[u].size() - 1));
    l[u] -= w[u];
    l[u] = max(l[u], 0ll);
    if (l[u] > ml) {
        l[u] = 0;
        r[u] = -1;
        return;
    }
    if (l[u] > r[u]) return;
    long long ll = l[u] - 1, rr = r[u] + 1;
    while (ll < rr - 1) {
        long long mid = ll + rr >> 1;
        long long sum = 0;
        for (int v : g[u]) sum += max(0ll, l[v] - mid);
        if (sum <= w[u] - mid * ((long long)g[u].size() - 1)) ll = mid;
        else rr = mid;
    }
    r[u] = min(r[u], ll);
}

inline void Solve() {
    for (int i = 1;i <= n;i++) {
        for (int x : g[i]) w[i] -= w[x];
    }
    Dfs(1);
    //cerr << l[1] << " " << r[1] << endl;
    if (l[1] <= r[1]) cout << "Huoyu\n";
    else cout << "Shuiniao\n";
}

inline void Clear() {
    for (int i = 1;i <= n;i++) {
        g[i].clear();
        w[i] = l[i] = r[i] = 0;
    }
}

int main() {
    freopen("water7.in", "r", stdin);
    freopen("water.out", "w", stdout);
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int c, t;
    cin >> c >> t;
    while (t--) {
        Read();
        Solve();
        Clear();
    }
    return 0;
}