Aczy156

Algorithm2.4 树型dp

[TOC]

树型dp

题目风格：给出树上的每个节点的值，然后给出

思路：

  • 利用链式前向星存储
    • 对于n叉树的话，这样存储最好，因为这样在每一层的节点对于他的子叶遍历时直接用链式前向星挨个遍历即可
    • 对于二叉树的话，可以直接用二叉链表储存，用链式前向星也可以
  • 在递归当前节点时，递归他的所有叶子结点
  • 在递归回来之后，修改dp数组，递归出来之后其子树的值是被更新过的，所以此时可以进行更新

最大子树和

https://www.luogu.com.cn/problem/P1122

题目大意：获取该棵树中最大的子树和

对于该题：

  • 数据结构：链式前向星储存，然后通过维护一个dp[i]数组，表示第i个节点为根的子树的最大和。
  • dp状态转移方程：dp[x] = max(dp[x], dp[x]+dp[to]);
#include <iostream>
using namespace std;
const int maxn = 2e4+9;
int n, dp[maxn], in[maxn], ta, tb;
struct node {
    int to, next;
}edges[maxn<<1];int head[maxn], tot;

void addedge(int from, int to) {
    edges[++tot].to = to;
    edges[tot].next = head[from];
    head[from] = tot;
    in[to]++;
}

void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;
        tree_dp(to);
        dp[x] = max(dp[x], dp[x]+dp[to]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", dp+i);
    for (int i = 1; i < n; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(tb, ta);
    }
    for (int i = 1; i <= n; ++i)
        if (!in[i]) {
            tree_dp(i);
            printf("%d\n", dp[i]);
        }
    return 0;
}

https://www.luogu.com.cn/problem/P1352

题目大意：没有上司的晚会，某个节点出现的条件是上下节点不出现。（在树上体现出来就是上下不相邻），如何挑选树上节点使得快乐值最大

对于该题：

  • 数据结构：链式前向星储存，然后通过维护一个dp[i][j]数组，在i=0表示不取当前这个节点的时候所获的的值 i=1表示取这个节点所获得的值
  • dp状态转移方程：dp[0][x] += max(dp[0][to], dp[1][to]); dp[1][x] += dp[0][to];
#include <iostream>
using namespace std;
const int maxn = 6e3+9;
int n, dp[5][maxn], in[maxn], ta, tb;
struct node {
    int to, next;
}edges[maxn<<1];int head[maxn], tot;

void addedge(int from, int to) {
    edges[++tot].to = to;
    edges[tot].next = head[from];
    head[from] = tot;
    in[to]++;
}

void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;
        tree_dp(to);
        dp[1][x] += dp[0][to];
        dp[0][x] += max(dp[1][to], dp[0][to]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &dp[1][i]);
    for (int i = 1; i <= n-1; ++i) {
        scanf("%d%d", &ta, &tb);
        addedge(tb, ta);
    }
    for (int i = 1; i <= n; ++i)
        if (!in[i]) {tree_dp(i);printf("%d\n", max(dp[0][i],dp[1][i]));}
    return 0;
}

具有背包思想的树形dp

题目风格：在树上截取有限的，有树形关系的部分。

// 不同于普通背包，普通背包是离散的，相互节点之间并没有必要联系的关系

https://www.luogu.com.cn/problem/P2014

题目大意：有先后关系，需要是一条树上的前后关联，然后问最大的和

#include <iostream>
using namespace std;
const int maxn = 305;
int n, dp[maxn][maxn], ta, tb, q;
struct node {
    int to, next;
}edges[maxn];int head[maxn], tot;

void addedge(int from, int to) {
    edges[++tot].to = to;
    edges[tot].next = head[from];
    head[from] = tot;
}

void tree_dp(int x) {
    for (int i = head[x]; i; i=edges[i].next) {
        int to = edges[i].to;
        tree_dp(to);
        for (int j = q+1; j >= 1; --j)
            for (int k = 0; k < j; ++k)
                dp[j][x] = max(dp[j][x], dp[k][to]+dp[j-k][x]);
    }
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &ta, &tb);
        dp[1][i] = tb;
        addedge(ta, i);
    }
    tree_dp(0);
    printf("%d\n", dp[q+1][0]);
    return 0;
}
Posted on Feb 1, 2021