树形 DP 练习 1

· 2023-08-31 · # 动态规划 # 树形 DP # 练习

P1352

设 $f_{i, 0/1}$ 表示第 i 个人去或者不去（0 常用来表示不去，1 常用来表示去）舞会所能获得的最大的快乐指数，则有：

f_{i, 0} = \sum\limits_{j \in son_i} \max \{f_{j, 0}, f_{j, 1}\}

f_{i, 1} = \sum\limits_{j \in son_i} f_{j, 0}

注： $f_{i, 0}$ 一般题目中没有限制，按照题目要求中转移即可； $f_{i, 1}$ 由于是表示第 i 个人去了舞会，所以只能由他没有去舞会的所有直接下属（即所有儿子节点）转移而来

Solution

std::function<void(int, int)> dp = [&](int x, int fa) {
    f[x][0] = 0;
    f[x][1] = r[x];

    for (int i = head[x]; i; i = e[i].nxt) {
        int y = e[i].to;
        if (y == fa) {
            continue;
        }
        dp(y, x);
        f[x][0] += std::max(f[y][0], f[y][1]);
        f[x][1] += f[y][0];
    }
};

P2015

设 $f_{i, j}$ 表示第 i 个节点保留 j 条边所能得到的最大苹果数。

类比树形 dp 背包转移方程 $f_{i, j} = \max \{ f_{i, j}, f_{tn, j - w_{tn}} + v_{tn} \}$ 有：
$f_{i, j} = \max \{ f_{i, j}, f_{tn,j - 1} + w_{tn} \mid tn \in son_i \}$

其中保留一条边可看做一件物品的重量为 1

小技巧1：让 $f_{tn, j} = f_{i, j}$ 即可实现 $\mathrm O (n^2)$ dp。

小技巧2：边权转点权的时候可以将边权给深度较大的节点，可以保证正确性。

Solution

std::function<void(int, int)> dp = [&](int x, int fa) {
    for (int i = head[x]; i; i = e[i].nxt) {
        int tn = e[i].to;
        if (tn == fa) {
            continue;
        }
        for (int j = 1; j <= q; ++j) {
            f[tn][j] = f[x][j];
        }
        dp(tn, x);
        for (int j = q; j >= 1; --j) {
            f[x][j] = std::max(f[x][j], f[tn][j - 1] + w[tn]);
        }
    }
};

P2014

树形 dp 背包例题

代码，转移方程同上题

P1122

54pts 百思不得其解

看了题解后发现读边的时候应该是读入 n - 1 条边，我读成了 n 条边，然后就过了（我：！@#￥%……&**

设 $f_i$ 表示 i 节点的最大子树和，有：

$f_i = w_i + \sum\limits_{j \in son_i} \max \{f_j, 0\}$

直接 $\mathrm O (n)$ dp 即可

P1613

没仔细读题，以为是颗树，结果是 DAG

思路其实很简单，如果两点之间的路径长度恰为 $2^k$ 那么就在这两个点之间连边，然后跑一次 bfs 即可。

由于在 maxlongint 范围，因此 k 的最大值为 64，边数为 $\mathrm O(w \cdot n^2 + m)$ 的级别，其中 $w = 64$

所以时间复杂度为 $\mathrm O(w \cdot n^3 + (w \cdot n^2 + m) \log n) = \mathrm O(w \cdot n^3 + m \log n)$ 可以通过本题

Solution

#include <bits/stdc++.h>

using ll = long long;

constexpr int inf = 0x7f7f7f7f;

template<typename T>
using G = std::vector<std::vector<T>>;

auto main()->int {
    #ifndef fastio
        std::cin.tie(nullptr)->sync_with_stdio(false);
    #endif
    
    // freopen("log.txt", "w", stderr);

    int n, m;
    scanf("%d %d", &n, &m);

    std::vector<std::array<int, 2>> e = {{0, 0}};
    int cnt = 0;
    std::vector<int> head(n + 1, 0);
    auto add = [&](int x, int y) {
        e.push_back({y, head[x]}), head[x] = ++cnt;
    };

    G<std::array<int, 65>> g1(n + 1, std::vector<std::array<int, 65>>(n + 1, std::array<int, 65>{}));
    G<int> g2(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        g1[a][b][0] = 1;
        g2[a][b] = 1;
    }

    for (int step = 1; step <= 64; ++step) {
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (g1[k][j][step - 1] && g1[j][i][step - 1]) {
                        g1[k][i][step] = 1;
                        g2[k][i] = 1;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (g2[i][j]) {
                add(i, j);
            }
        }
    }

    auto bfs = [&]() {
        std::vector<int> v(n + 1, 0);
        std::vector<int> d(n + 1, inf);
        std::priority_queue<std::array<int, 2>> q;

        d[1] = 0;
        q.push({0, 1});
        while (!q.empty()) {
            int x = q.top()[1];
            q.pop();

            if (v[x]) {
                continue;
            }
            v[x] = 1;
            for (int i = head[x]; i; i = e[i][1]) {
                int tn = e[i][0];
                if (d[tn] > d[x] + 1) {
                    d[tn] = d[x] + 1;
                    q.push({-d[tn], tn});
                }
            }
        }

        return d[n];
    };

    printf("%lld", bfs());
    
    return 0;
}

P1131

口胡一个

题目中所给数据为一颗普通的树，