dWoi Round 2 B 题解

· · 题解

Description

给定一棵树，每一条边有边权 t_i，每一个点有点权 w_i，t_i 对应的值决定这条边连接的两个点的值的大小关系（等于，不等于，没有关系），求满足所有 t_i 的关系且 w_i \in [1,R] 的点权赋值情况一共有多少种，并且求出最小的点权和。

注：本文有视频讲解，请在文章最下方查看 qwq。

Solution

两问分别考虑，都要考虑树形 dp。

第一问

设 f_{i,j} 为以 i 为根节点的子树且 w_i=j 时的答案。

设 k 为 i 的一个儿子，对边 (i,k) 的边权 t 分类讨论：

f_{i,j}=f_{i,j} \times \sum\limits_{p=1,p \ne j}^Rf_{k,p} f_{i,j}=f_{i,j} \times \sum\limits_{p=1}^Rf_{k,p} f_{i,j}=f_{i,j} \times f_{k,j}

答案即为 \displaystyle \sum\limits_{i=1}^R f_{1,i}。

第二问

设 f_{i,j} 为以 i 为根节点的子树且 w_i=j 时的答案。

设 k 为 i 的一个儿子，对边 (i,k) 的边权 t 分类讨论：

f_{i,j}=\min\limits_{p=1,p \ne j}^{R}\{f_{k,p}\}+j f_{i,j}=\min\limits_{p=1}^R\{f_{k,p}\}+j f_{i,j}=f_{k,j}+j

答案即为 \min\limits_{i=1}^R f_{1,i}。

优化

（思路来自 Euler_Pursuer）

如果按照上面的方法打代码，你会发现最终复杂度为 \mathcal O(nR^2)，过不了。

我们尝试把 \mathcal O(nR^2) 优化为 \mathcal O(nR)。

操作比较简单，对于第一问，预处理前缀和，对于第二问预处理 \min 的前缀和后缀即可。

总结

本题为一道简单的树形 dp，只要想清楚升维就没了。

下面是代码的主要部分，仅供参考（写的很难看）：

void dfs1 (int cur, int fa) {
    for (int i = 1; i <= r; i++) dp1[cur][i] = 1ll;
    bool isleaf = false;
    for (int p = head[cur]; p; p = e[p].v) {
        if (e[p].u == fa) continue;
        isleaf = true;
        dfs1(e[p].u, cur);
        int t = e[p].w;
        if (t == 0) {
            for (int i = 1; i <= r; i++) {
                long long sum = s[e[p].u][r];
                sum += Mod;
                sum -= dp1[e[p].u][i];
                sum %= Mod;
                dp1[cur][i] *= sum;
                dp1[cur][i] %= Mod;
            }
        }
        if (t == 1) {
            for (int i = 1; i <= r; i++) {
                dp1[cur][i] *= s[e[p].u][r];
                dp1[cur][i] %= Mod;
            }
        }
        if (t == 2) {
            for (int i = 1; i <= r; i++) {
                dp1[cur][i] *= dp1[e[p].u][i];
                dp1[cur][i] %= Mod;
            }
        }
    }
    if (!isleaf)
        for (int i = 1; i <= r; i++)
            dp1[cur][i] = 1;
    for (int i = 1; i <= r; i++) {
        s[cur][i] = s[cur][i - 1] + dp1[cur][i];
        s[cur][i] %= Mod;
    }
}

void dfs2 (int cur, int fa) {
    for (int i = 1; i <= r; i++) dp2[cur][i] = 1ll * i;
    for (int p = head[cur]; p; p = e[p].v) {
        if (e[p].u == fa) continue;
        dfs2(e[p].u, cur);
        int t = e[p].w;
        if (t == 0) {
            for (int i = 1; i <= r; i++) {
                dp2[cur][i] += min(pre[e[p].u][i - 1], suf[e[p].u][i + 1]);
            }
        }
        if (t == 1) {
            for (int i = 1; i <= r; i++) {
                dp2[cur][i] += pre[e[p].u][r];
            }
        }
        if (t == 2) {
            for (int i = 1; i <= r; i++)
                dp2[cur][i] += dp2[e[p].u][i];
        }
    }
    pre[cur][0] = 0x3f3f3f3f;
    suf[cur][r + 1] = 0x3f3f3f3f;
    for (int i = 1; i <= r; i++) pre[cur][i] = min(pre[cur][i - 1], dp2[cur][i]);
    for (int i = r; i >= 1; i--) suf[cur][i] = min(suf[cur][i + 1], dp2[cur][i]);
}

视频讲解

您是否觉得文字太过枯燥？本人提供了不知道是否生动有趣的视频讲解 \downarrow

设置在 2021 年 8 月 23 日 17 点 30 分发布，因此可能提前看不到。