Menu
Article ACM

树形DP入门(持续更新中

NodeKey

NodeKey

• 7 min read 
<code class="language-null">以前在暑假集训的时候搞得最多的还是图论相关，如果碰到树形结果很多时候就直接用搜……当然绝大多数时候也都T了……（当时也不喜欢分析复杂度，真是个坏习惯……

树形DP，简单说还是在树上做决策，只要把基础DP掌握好了我想应该不会是什么难事，只是换个场地罢了……

0. 入门题 POJ 2342

题意：
某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系（当然不可能存在环），求邀请哪些人（多少人）来能使得晚会的总活跃指数最大。

思路：
定义数组dp[maxn][2],dp[k][0]表示第 k 人不去，dp[k][1] 表示第 k 人去。定义 son 为第 K 人的某个下属
我们从下往上分析，对于第 K 个人有以下去与不去两种情况

  • 假如 K 参加，那么对于他的每一个下属都不会去，那么就只能加上这个下属不去的这棵子树的值 dp[son][0]
  • 假如 K 不参加，那么他的下属可以选择去或者不去，当然我们要选择子树权值最大的 max(dp[son][0],dp[son][1])
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 10000;

vector<int> tree[maxn];
int n;
int dp[maxn][2];

void tree_dp(int cur, int pre)
{
    int sz = tree[cur].size();
    for (int i = 0; i < sz; i++) {
        int son = tree[cur][i];
        if (son != pre) {
            tree_dp(son, cur);
            dp[cur][1] += dp[son][0];
            dp[cur][0] += max(dp[son][0], dp[son][1]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            cin >> dp[i][1];
            tree[i].clear();
            dp[i][0] = 0;
        }
        while (cin >> u >> v) {
            if (u == 0 && v == 0)
                break;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        tree_dp(1, -1);
        printf("%d\n", max(dp[1][0], dp[1][1]));
    }
    return 0;
}

顺便值得一提的是：
我看了很多网上的题解，无一都选择先找到树的根节点，然后从根节点进行向下dp。这样或许可以降低复杂度
因为出数据都习惯把初始树建的平衡一些……
但对于一棵树来说，无论你把哪一个节点定为根节点，它都能转化成另外一棵树，在这里是没有什么影响的。更何况，极端数据不排除会有极度不平衡的情况，其结果是一样的，该A的A，该WA的WA……还不如偷懒一点，提升一点码速。

1.1 向下递推 POJ 1947 Rebuilding Roads

题意：
给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为p个。

思路：
定义数组 dp[root][n] 表示以 当前节点为 root 节点，含有 n 个点所需删除的最小边数。
显然 dp[root][1]=root节点的所有孩子的个数+1（一个父亲节点），但是对于一棵树的根节点是没有父亲节点的。我这里先不考虑父亲节点，到最后再加上去。

初始状态已经确定，关键的还是 转移方程 ：

dp[root][n] = min(dp[root][n]，dp[root][n-k]+dp[root.son][k]-1);

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 160;
int n, p, ans;
vector<int> key[maxn];
int dp[maxn][maxn];

int tree_dp(int root)
{
    int total = 1, sz = key[root].size();
    for (int i = 0; i < sz; i++)
        total += tree_dp(key[root][i]);
    dp[root][1] = sz;
    for (int j = 0; j < sz; j++) {
        int son = key[root][j];
        for (int i = min(p, total); i > 1; i--) {
            for (int k = 1; k < i; k++) {
                dp[root][i] = min(dp[root][i], dp[root][i - k] + dp[son][k] - 1);
            }
        }
    }
    ans = min(ans, dp[root][p] + (root != 1));
    return total;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u, v;
    while (cin >> n >> p) {
        for (int i = 1; i <= n; i++)
            key[i].clear();
        memset(dp, 0x3f, sizeof dp);
        for (int i = 1; i < n; i++) {
            cin >> u >> v;
            key[u].push_back(v);
        }
        ans = 0x3f3f3f3f;
        tree_dp(1);
        cout << ans << endl;
    }
    return 0;
}
1.2 树上的01背包 HDU 1561

题意：
给你一个森林，每个节点都赋予一个权值。让你取 m 个节点，使得节点和最大。
当然，取节点也是有条件的： 如果你要取走这个节点，那你必须先取走它的父亲节点。

思路：
额外增加一个超级根节点，让这片森林里的每棵树的根节点都成为这个超级根节点的孩子，以形成一棵树。
再与上题一样，在树上不断向下递推即可

转移方程： dp[root][i] = max( dp[root][i] , dp[root][i-k] + dp[root.son][k])

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long

using namespace std;

const int maxn = 205;
int n, idx, ans, m;
int head[maxn], dp[maxn][maxn], val[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void init()
{
    for (int i = 0; i <= n; i++) {
        head[i] = -1;
        for (int j = 0; j <= n; j++)
            dp[i][j] = 0;
    }
    idx = val[0] = 0;
    m++;
}

void treeDP(int root)
{
    dp[root][1] = val[root];
    for (int it = head[root]; ~it; it = edges[it].nxt) {
        int v = edges[it].to;
        treeDP(v);
        for (int i = m; i >= 1; i--)
            for (int k = 1; k < i; k++)
                dp[root][i] = max(dp[root][i], dp[root][i - k] + dp[v][k]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int u;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;
        init();
        for (int i = 1; i <= n; i++) {
            cin >> u >> val[i];
            addEdge(u, i);
        }
        treeDP(0);
        cout << dp[0][m] << endl;
    }
    return 0;
}
1.3 树上的最大连续序列 POJ 1192

题意：
题目虽然是中文，但说的非常繁琐。
简单概括就是 给定一个平面整点集，点与点间在|x1-x2| + |y1-y2| = 1 时两点连通，且形成的图没有回路其实就是一棵树啦，每个点有一个可正可负的权值，求最大权和连通子图。

思路：
和一维的 求连续最大权值序列 是一个思路

转移方程： dp = max(dp, dp + son )

//好激动呀，这是第一道我自己独立写出来的树形DP

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>
#define ll long long

using namespace std;

const int maxn = 1005;
int n, idx, ans;
int head[maxn];

struct node {
    int x, y, w;
} nodes[maxn];

struct edge {
    int to;
    int nxt;
} edges[maxn << 1];

void addEdge(int u, int v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool judgeAdj(int u, int v)
{
    return abs(nodes[u].x - nodes[v].x) + abs(nodes[u].y - nodes[v].y) == 1;
}

void init()
{
    for (int i = 0; i <= n; i++)
        head[i] = -1;
    idx = ans = 0;
}

int treeDP(int cur, int pre)
{
    int dp = nodes[cur].w;
    for (int it = head[cur]; it != -1; it = edges[it].nxt)
        if (edges[it].to != pre) 
            dp = max(dp, dp + treeDP(edges[it].to, cur));
    return dp;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n) {
        init();
        for (int i = 0; i < n; i++)
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].w;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                if (judgeAdj(i, j)) {
                    addEdge(i, j);
                    addEdge(j, i);
                }
            }
        ans = treeDP(1, -1);
        cout << ans << endl;
    }
    return 0;
}
Share