树形 DP，顾名思义，就是在树上的 DP。因为树是一个递归定义的概念，所以，树形 DP需要在 DFS 中进行，所以有人说树形 DP 是一种记忆化搜索。（ZQW：没错就是我）

树上背包

这个类型的问题让我想起了背包问题中“有依赖的背包问题”，也就是说，这种背包问题的某些物品只有在选了前置物品的条件下才能选，具体的关系构成一棵树。

让我们来看一道例题：Luogu P2015 二叉苹果树。

这道题有两个要求，第一个是必须保留 $Q$ 条边，第二个是要求留下的边的权值加起来最大。

因为树的任何一个节点都可以作为根节点，所以这里我们默认 $1$ 为根节点（下文同理）。

那么，跟普通背包一样，$dp$ 数组第一维代表抉择的物品，第二维代表背包容量，令 $dp_{u,j}$ 为根节点为 $u$ 的子树上保留 $j$ 条边能达到的最大权值和。

那该怎么状态转移呢？

首先，当我们求 $dp_{u,?}$ 的时候，肯定是要知道它所有子节点的答案。所以，DFS 向下递归的语句应该在状态转移语句的前面。

其次，和普通背包一样，每一个物品（这里是每一条边）都有选和不选两种情况。只是这里，令 $u$ 的一个子节点为 $v$，假如 $(u,v)$ 这一条边没取，那以 $v$ 为根节点的这一棵子树都取不了了，所以只能忽略这棵子树，答案还是原来的 $dp_{u,i}$。而取的时候，情况就比较复杂了，我们需要考虑一下这棵子树到底要保留多少条，所以我们还需要一层循环 $k$，代表这棵子树上保留 $k$ 条边，$(u,v)$ 有一条边，所以剩下的所有子树加起来有 $j-k-1$ 条边。所以对于每一个子节点 $v$，状态转移方程如下：

这里要注意：

  1. $k$ 到 $0$ 结束，$k=0$ 是不取的情况。
  2. 因为计算 $dp_{u,j}$ 时需要用到 $dp_{u,j-k-1}$ 的值，而 $dp_{j-k-1}$ 是其它子树上的最大权值之和，不能算上 $v$ 这一棵子树，所以 $j,k$ 枚举的顺序应该是倒着枚，以免重复（和 01 背包滚动数组背包容量要倒过来枚举是一样的道理）。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

struct node {
    int to, val;
};
int n, q, dp[105][105];
bool b[105];
std::vector<node> G[105];

inline int max(int x, int y) { return x > y ? x : y; }

void dfs(int i) {
    b[i] = 1;
    int len = G[i].size();
    if(len == 1)
        return;
    rep(v, 0, len - 1) {
        if(!b[G[i][v].to]) {
            dfs(G[i][v].to);
            dep(j, q, 0)
                dep(k, j - 1, 0)
                    dp[i][j] = max(dp[i][j], G[i][v].val + dp[G[i][v].to][k] + dp[i][j - k - 1]);
        }
    }
    return;
}

int main() {
    scanf("%d %d", &n, &q);
    int u, v, w;
    rep(i, 1, n - 1) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back(node({v, w}));
        G[v].push_back(node({u, w}));
    }
    dfs(1);
    printf("%d", dp[1][q]);
    return 0;
}

变式练习：

  • 「CTSC1997」选课

    和例题基本上一样，只是这道题给的是一个森林而非一棵树。处理方法也很简单，只需要建一个 $0$ 号节点，把所有树的根节点连上去，然后以 $0$ 为根处理就行了。

树的直径

树的直径就是一棵树上最长的链，所以一棵树上可能不止一条直径。

只求长度

例题如下：

如果一个数 $x$ 的约数和 $y$（不包括他本身）比他本身小，那么 $x$ 可以变成 $y$，$y$ 也可以变成 $x$。例如 $4$ 可以变为 $3$，$1$ 可以变为 $7$。限定所有数字变换在不超过 $n$ 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

这道题转换挺巧妙的，该怎么看出来这是个求树的直径的问题呢？

其实，我们只需要画一张图，把数字作为节点，可以相互变换的数字连在一起就可以了：

这个时候就有人问了：那怎么证明这个图里没有环？

令对一个数 $a$ 求约数和的操作为 $f(a)$。假设 $f(x)=y,f(y)=z$，那如果想要构成一个环，就要求 $f(x)=z$，或者 $f(z)=x$。

第一种情况很好排除，因为只有 $y=z$ 时才能构成环，而 $f(y)=z$，所以，只有像 $6$ 那样的“完全数”才能满足。但是，既然 $y$ 已经是完全数了，那么说明 $x=y$，实际上这是一个自环，对结果没有影响，我们直接忽略掉它。

第二种情况乍一看不太好整，但是注意到题目要求可以发现 $x>y>z$，然后又要求 $f(z)<z$，很显然 $f(z)\neq x$。（所以第一种情况也可以直接排除了，因为完全数是不被允许的）

好的，现在我们可以证明这张图是一棵树了，接下来的事情就简单了。因为不能重复，所以我们只能从一个节点走到另一个节点不能回头，那只需要找到树上最长的链就行了，也就是树的直径。

那回归正题：怎么求树的直径的长度？

我们知道，一个节点上能产生的影响经过此节点的最长链的长度的链只有三条：

设节点 $u$ 往下的最长链长度为 $d1_u$，次长链为 $d2_u$，往上的链（经过它的父节点）为 $up_u$，那么这条链的长度要么是 $d1_u+d2_u$，要么是 $d1_u+up_u$，反正不可能是 $d2_u+up_u$（因为保证 $d1_u\ge d2_u$），所以我们可以发现是一定有 $d1_u$ 的。

那么，对于 $u$ 的所有父节点 $r$（这个 $r$ 指的不是某一个节点，而是所有 $u$ 的直系父节点，可以是它的爸爸，也可以是它的爷爷，一直往上追溯到根节点），$d1_u+up_u$ 和 $\max\{d1_r+d2_r\}$ 是一样的，因为后者其实包含了 $d1_u$ 和所有 $up_u$ 中的所有情况。这个大家自己画画图就知道了，用语言不太好描述 qwq。

所以，我们只需要遍历一下每一个节点的 $d1,d2$ 之和就可以了。

那 $d1,d2$ 该怎么求呢？

这就回归到了树形 DP。我们还是 DFS 往下找，遍历每一个节点 $u$ 的所有子节点 $v$。对于每一个子节点，先对它 DFS，此时每一个 $v$ 都有自己的 $d1_v$，我们只需要找到最大的两个 $d1_v$ ，再加上 $1$ 就可以求出 $d1_u$ 和 $d2_u$。

那为什么不能用 $d2_v$ 来更新呢？确实有这种情况：某个节点的最长链和次长链的下一个节点都在一个子节点上。但是我们的要求是：这两条链不能重合！ 不然树的直径就经过重复的节点了，所以我们不能用 $d2_v$ 来更新 $d1_u$ 和 $d2_u$。

所以，光求长度跟 $up$ 数组没有半毛钱关系。

这道题的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)5e4 + 5;

int n, ans, h1[maxn], h2[maxn], q[maxn];
std::vector<int> G[maxn];
bool b[maxn];
inline int max(int x, int y) { return x > y ? x : y; }

inline int mk(int x) {
    int s = 0, p = floor(sqrt(x));
    rep(i, 1, p)
        s += x % i ? 0 : i + x / i;
    if(p * p == x)
        s -= p;
    return s - x;
}

void dfs(int u) {
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v]) {
            dfs(v);
            if(h1[v] + 1 > h1[u]) {
                h2[u] = h1[u];
                h1[u] = h1[v] + 1;
            } else if(h1[v] + 1 > h2[u])
                h2[u] = h1[v] + 1;
        }
    }
    ans = max(ans, h1[u] + h2[u]);
    return;
}

int main() {
    scanf("%d", &n);
    rep(i, 2, n)
        q[i] = mk(i);
    rep(i, 2, n) {
        if(q[i] > i)
            continue;
        G[i].push_back(q[i]);
        if(i != q[i])
            G[q[i]].push_back(i);
    }
    /*
    rep(i, 1, n) {
        printf("%d: ", i);
        rep(j, 0, (int)G[i].size() - 1)
            printf("%d ", G[i][j]);
        printf("\n");
    }
    */
    dfs(1);
    printf("%d", ans);
    return 0;
}

提交记录 #1145000。

求直径上的节点

来看上道题的加强版：要求我们输出所有在树的直径上的节点编号。

思路还是那个思路，不过这下我们就需要求 $up$ 了，这样我们才能知道每一个节点上的最长链到底等不等于树的直径的长度。

那怎么求某个节点 $u$ 的 $up$ 值呢？有两种情况：

  1. 先从它父节点 $r$ 的 $up$ 值代表的路径走到 $r$，再走到 $u$，$up_u=up_r+1$；
  2. 先从 $r$ 的 $d1$ 值代表的路径走到 $r$，再走到 $u$，$up_u=d1_r+1$。

过程就是这样吗？不完全是，请看图：

我们在更新 $up_4$ 的值时，会发现 $d1_2+1=4$，但是实际上很明显 $up_2=3$。这是因为 $d1_2$ 这一条路径会经过 $4$ 节点，而树的直径要求不能经过重复的节点，于是就出问题了。

解决方案是：当判断到 $d1_r$ 这条路径经过 $u$ 的时候，把 $d1_r+1$ 更换为 $d2_r+1$ 即可，如果 $d1_r$ 经过另外 $u$，那么 $d2_r$ 一定不经过 $u$。

输出答案时一个节点一个节点地判断，如果经过这个节点的最长链长度等于树的直径，那就输出。

代码如下（调了好久 qwq）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)2e5 + 5;

int n, ans, d1[maxn], d2[maxn], up[maxn]; // d1 为向下最长链，d2 为向下次长链，up 为第一步先到父节点之后不再折返回来的最长链 
std::vector<int> p, G[maxn]; // G 存图，p 存答案 
bool b[maxn]; // 标记走过的节点，以免重复走到 

inline int max(int x, int y) { return x > y ? x : y; }

void dfs1(int u) { // 从下往上递归，求解 d1, d2 和直径的长度 
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) { // 遍历此节点的所有子节点 
        int v = G[u][i];
        if(!b[v]) {
            dfs1(v); 
            // 用 d1[v] 去更新 d1[u] 和 d2[u]
            // ※注意不能用 d2[v]
            if(d1[v] + 1 > d1[u]) {
                d2[u] = d1[u];
                d1[u] = d1[v] + 1;
            } else if(d1[v] + 1 > d2[u])
                d2[u] = d1[v] + 1;
            ans = max(ans, d1[u] + d2[u]); // 更新最长链的长度，为了方便没有计算 u 
        }
    }
    return;
}

void dfs2(int u) { // 从上往下递归，求解 up 
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v]) {
            if(d1[v] + 1 == d1[u]) // 这说明 u 的最长链经过了 v，因为会重复走 v，所以不能用 d1 更新 up 而是应该用 d2 
                up[v] = max(up[u], d2[u]) + 1;
            else // 其余情况就正常更新 
                up[v] = max(up[u], d1[u]) + 1;
            dfs2(v);
        }
    }
    return; 
}

/*
void debug() {
    puts("--------------DEBUG--------------");
    printf("ans = %d\n", ans);
    printf("num  d1  d2  up\n");
    rep(i, 1, n)
        printf("%-5d%-4d%-4d%-4d\n", i, d1[i], d2[i], up[i]);
    puts("---------------------------------\n");
    return;
}
*/

int main() {
    scanf("%d", &n);
    int u, v;
    rep(i, 1, n - 1) {
        scanf("%d %d", &u, &v);
        ++u, ++v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1);
    memset(b, 0, sizeof(b));
    dfs2(1);
    // debug();
    rep(i, 1, n) {
        if(d1[i] + max(up[i], d2[i]) == ans) // i 在最长链上
            p.push_back(i);
    }
    int anslen = p.size() - 1;
    rep(i, 0, anslen)
        printf("%d\n", p[i] - 1);
    return 0;
}

与相邻节点有关的树形 DP

实在不知道应该写什么名字才写的这个。

这种树形 DP 一般来说会有一维来记录此节点的状态（比如说要在树上染色，开一维代表这个节点有没有染色时候的状态）。

例题 1

Luogu P2016 战略游戏

通过读题我们知道，当一条边的两个端点中有至少一个节点放了士兵，这条边就被监视了，所以可以定义 $dp_{u,0/1}$ 为把 $u$ 作为根节点时有/没有放士兵，而且这个子树上的所有边都被监视了的时候这课子树上能放的最少的士兵数量。

状态转移如下：

  • $dp_{u,1}$：$u$ 已经放了士兵，所以它的子节点有没有放士兵都没有关系，方程是 $dp_{u,1}=\min\{dp_{v,0},dp_{v,1}\}$；
  • $dp_{u,0}$：$u$ 没放士兵，所以它的儿子必须自力更生，方程是 $dp_{u,0}=\min\{dp_{v,0}\}$。

然后就没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 1505;

int n, dp[maxn][2];
bool G[maxn][maxn], b[maxn];

inline int min(int x, int y) { return x < y ? x : y; }

void dfs(int t) {
    b[t] = 1;
    rep(i, 1, n) {
        if(G[t][i] && !b[i]) {
            dfs(i);
            dp[t][0] += dp[i][1];
            dp[t][1] += min(dp[i][0], dp[i][1]);
        }
    }
    ++dp[t][1];
    return;
}

int main() {
    scanf("%d", &n);
    int u, v, s;
    rep(i, 1, n) {
        scanf("%d %d", &u, &s);
        ++u;
        rep(j, 1, s) {
            scanf("%d", &v);
            ++v;
            G[u][v] = G[v][u] = 1;
        }
    }
    dfs(1);
    printf("%d", min(dp[1][0], dp[1][1]));
    return 0;
}

例题 2

基本上和例题 $1$ 一样，不过监视的对象从边换成了节点，然后每个节点安排士兵的时候都有一个输入给出的权值。

权值这个倒是没什么影响，但是从边变到节点，就出了一个问题，对于一个节点，只要它的儿子、它的父亲和它本身三者中有至少一个放了士兵，那这个节点就是合法的。所以，这道题的第二维有三种情况：

  • $dp_{u,0}$ 代表 $u$ 节点自己就放了士兵，它的子节点 $v$ 不管状态是啥都是允许的，所以 $dp_{u,0}=\max{dp_{v,0},dp_{v,1},dp_{v,2}}$。
  • $dp_{u,1}$ 代表 $u$ 节点的父节点放了士兵，而它自己不放士兵，所以它的子节点就不能依靠父节点（也就是 $u$），$dp_{u,1}=\max\{dp_{v,0},dp_{v,2}\}$。
  • $dp_{u,2}$ 代表 $u$ 的至少一个子节点放了士兵，它自己不放。注意不是每个子结点都必须放，只需要有一个就行了，而且此时的子节点也不能依靠父节点。 所以 $dp_{u,2}$ 相较于 $dp_{u,1}$，只相差了一个子节点的贡献。我们通过一个循环找出一个子节点，使得它放了士兵和它没放士兵时相差的贡献值最小，这样就能保证 $dp_{u,2}$ 尽量接近 $dp_{u,1}$，也就是保障最优情况。方程是 $dp_{u,2}=dp_{u,1}-\min\{dp_{v,0},dp_{v,2}\}$。

最后求答案的时候注意，根节点没有父节点，所以最终答案是 $\max\{dp_{1,0},dp_{1,2}\}$，没有 $dp_{1,1}$。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 1505;

int n, dp[maxn][3], m[maxn];
bool G[maxn][maxn], b[maxn];

inline int min(int x, int y) { return x < y ? x : y; }

void dfs(int u) {
    b[u] = 1;
    int Min = 1 << 30;
    rep(v, 1, n) {
        if(G[u][v] && !b[v]) {
            dfs(v);
            dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
            dp[u][1] += min(dp[v][0], dp[v][2]);
            Min = min(Min, dp[v][0] - min(dp[v][0], dp[v][2]));
        }
    }
    dp[u][0] += m[u];
    dp[u][2] = dp[u][1] + Min;
    return;
}

int main() {
    scanf("%d", &n);
    int u, v, s, num;
    if(n == 1) {
        scanf("%d %d", &u, &num);
        printf("%d", num);
        return 0;
    }
    rep(i, 1, n) {
        scanf("%d %d %d", &u, &num, &s);
        m[u] = num;
        rep(j, 1, s) {
            scanf("%d", &v);
            G[u][v] = G[v][u] = 1;
        }
    }
    dfs(1);
    int ans = min(dp[1][0], dp[1][2]);
    printf("%d", ans);
    return 0;
}

例题 3

Luogu P1352 没有上司的舞会

对于一个人来说还是两种情况，要么就是他自己不来，要么就是他的上司不来。

  • 他来的话，他的所有部下都不能来。
  • 他不来的话，他的部下既可以来也可以不来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = 6005;

int n, p[maxn], dp[maxn][2];
std::vector<int> G[maxn];
bool b[maxn];

inline int max(int a, int b) { return a > b ? a : b; }

void dfs(int u) {
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v]) {
            dfs(v);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
    dp[u][1] += p[u];
}

int main() {
    scanf("%d", &n);
    rep(i, 1, n)
        scanf("%d", &p[i]);
    int u, v;
    rep(i, 1, n - 1) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1);
    printf("%d", max(0, max(dp[1][0], dp[1][1])));
    return 0;
}

例题 4

「CQOI2009」叶子的染色

这题的题面说得很迷惑，其实你可以想象成拿一桶水，水最开始是无色的，从根节点往下流，最后流到叶子节点上，水的颜色遇到染色的节点就会变成节点的颜色（只有黑和白），但是这一股水颜色的变化只对以此节点为根的这棵子树有影响。要求确定每一个叶子节点收到的水的颜色，问你最少要让多少个节点染色。

$dp_{u.0/1}$ 代表经过 $u$ 节点的水流的颜色是黑/白时这棵子树上最少染色节点的数量。

我们先假设我们给 $u$ 的子节点 $v$ 染了色，所以最后需要加上 $1$。然后我们发现，如果水流经过 $u$ 和 $v$ 的颜色是一样的，那 $v$ 就可以不染色，所以在动规方程里，这种情况需要 $-1$。

叶子节点的初始化，颜色为 $c_u$ 时等于 $1$，不是 $c_u$ 的那一个设成极大值即可。

然后我们随便选一个非叶子节点作为根节点，把水倒下去就可以了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)1e4 + 5;
const int inf = 1 << 30;

int n, m, ans, c[maxn], dp[maxn][2];
std::vector<int> G[maxn];
bool b[maxn];

inline int min(int x, int y) { return x < y ? x : y; }
inline int f(int x) { return x ? 0 : 1; }

void dfs(int u) {
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v]) {
            dfs(v);
            dp[u][0] += min(dp[v][0] - 1, dp[v][1]);
            dp[u][1] += min(dp[v][1] - 1, dp[v][0]);
        }
    }
    ++dp[u][0], ++dp[u][1];
    if(u <= m) {
        dp[u][c[u]] = 1;
        dp[u][f(c[u])] = inf;
    }
    return;
}

int main() {
    scanf("%d %d", &n, &m);
    rep(i, 1, m)
        scanf("%d", &c[i]);
    int u, v;
    rep(i, 1, n - 1) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(m + 1);
    printf("%d", min(dp[m + 1][0], dp[m + 1][1]));
    return 0;
}

例题 5

「HNOI2003」消防局的设立

人类在 2003 年许下的美好愿望，到了 2020 年终于是没实现。

这题乍一看跟例 $2$ 好像也没啥区别是吧？

怎么可能！虽然保管的距离只是从 $1$ 变成了 $2$，但是要麻烦多了。

这题有两种做法，一个是树形 DP，有五种状态（它爷爷，它爸爸，它自己，它儿子，它孙子），因为笔者不会，所以请大家自行推导；还有一种就是今天要介绍的贪心方法，这个贪心的策略浓缩成一句话就是：从下往上找，如果不满足条件，就在这里修一个消防站。

首先 DFS 预处理每一个节点的深度，然后再按照深度从大到小排序。注意这里因为要排序，所以记录节点深度的数组 $deep$ 应该是一个结构体，分别存深度大小和是哪一个节点。

我们需要两个数组，一个是 $q$，$q_u$ 代表排完序之后 $u$ 这个节点和它的深度在 $deep$ 数组的位置（下标，这个数组是为了方便寻找某个节点的父节点，这样可以直接找到某个节点的深度），另一个是 $data$，$data_u$ 代表现在离 $u$ 最近的一个消防站有多远。

按照深度从大到小枚举节点，然后判断这个节点有没有被消防站覆盖，如果没有就盖一个，顺便更新一下它父亲和爷爷的 $data$ 值。

然后就没了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

struct node {
    int num, id;
} deep[1005];

int n, ans, data[1005], q[1005];
std::vector<int> G[1005];
bool b[1005], build[1005];

bool operator<(node x, node y) { return x.num > y.num; }

inline int min(int x, int y) { return x < y ? x : y; }

void getdeep(int u, int dep) {
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v])
            getdeep(v, dep + 1);
    }
    deep[u].id = u;
    deep[u].num = dep;
    return;
}

inline int fa(int u) { // 找 u 的父亲
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(deep[q[v]].num == deep[q[u]].num - 1)
            return v;
    }
    return 1;
}

int main() {
    memset(data, 0x3f3f3f, sizeof(data));
    scanf("%d", &n);
    int v;
    rep(u, 2, n) {
        scanf("%d", &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    getdeep(1, 0);
    std::stable_sort(deep + 1, deep + n + 1);
    rep(i, 1, n)
        q[deep[i].id] = i;
    rep(i, 1, n) { 
    // *需要注意，这个循环里面我们要判断修不修消防站的是 gf 节点，所以我们需要知道它两代及以内的所有节点，即 u, ft, ggf, gggf
        int ft = fa(deep[i].id);
        int gf = fa(ft);
        if(!build[ft] && !build[gf] && data[deep[i].id] > 2 && data[ft] > 1 && data[gf] > 0) {
            ++ans;
            // printf("%d: build %d\n", deep[i].id, gf);
            build[gf] = 1;
            data[deep[i].id] = min(data[deep[i].id], 0);
            int ggf = fa(gf);
            int gggf = fa(ggf);
            data[ggf] = min(data[ggf], 1);
            data[gggf] = min(data[gggf], 2);
        }
    }
    printf("%d", ans);
    return 0;
}

换根 DP

换根 DP，就是在求解的过程中以不同的节点为根来求解问题。

看例题：Luogu P3478 STA-Station。

求解这个问题需要知道以每个节点为根时的深度总和，但是我们不可能每一个节点都 DFS 一次，这样就超时了。但是，有没有方法可以只 DFS 一个节点，然后根据这个节点的答案去求解其它节点的答案？

这张图是我们把根节点从 $2$ 转移到 $4$ 的过程。可以发现，在 $4$ 为根节点时，以 $2$ 为根节点的子树（红色框）所有节点到根节点的距离都会加上 $w$；而在 $2$ 为根节点时，以 $4$ 为根节点的子树（蓝色框）所有节点到根节点的距离都会减少 $w$，只要知道两棵子树分别有多少个节点，就可以根据 $2$ 的答案求解出 $4$ 的答案，公式是 $ans_4=ans_2+size(red)\times w-size(blue)\times w$。

所以，我们可以先打一个预处理的 DFS 函数，把以 $1$ 为根节点时每一棵子树的节点总量都求出来。设 $num_i$ 为以 $1$ 为根节点，子树根节点为 $i$ 时这棵子树节点的数量。

当然，在实际求解的时候，因为求解过程中转移时的根节点不一定是 $1$，但是某个子树（假设根节点为 $u$）里面包含我们预处理时的根节点 $1$。所以这个子树的节点总数就不能直接用 $num_u$，而应该用 $n-num_v$（$v$ 为 $u$ 的另一个子节点，以上图举例，$u=2,v=4$）。

然后就是代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <vector>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)

const int maxn = (int)1e6 + 5;

int n, ans, p, deepsum[maxn], num[maxn];
bool b[maxn];
std::vector<int> G[maxn];

inline int min(int x, int y) { return x < y ? x : y; }

void dfs1(int u, int s) { // 预处理
    b[u] = 1;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v]) {
            dfs1(v, s + 1);
            deepsum[u] += deepsum[v];
            num[u] += num[v];
        }
    }
    deepsum[u] += s;
    ++num[u];
    return;
}

void dfs2(int u, int Num) { // 换根 DP
    b[u] = 1;
    if(ans < Num) {
        ans = Num;
        p = u;
    } else if(ans == Num)
        p = min(u, p);
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(!b[v])
            dfs2(v, Num + n - (num[v] << 1));
    }
    return;
}

signed main() {
    scanf("%lld", &n);
    int u, v;
    rep(i, 1, n - 1) {
        scanf("%lld %lld", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1, 0);
    memset(b, 0, sizeof(b));
    ans = deepsum[1];
    p = 1;
    dfs2(1, deepsum[1]);
    printf("%lld", p);
    return 0;
}

变式：

  • 「USACO10MAR」Great Cow Gathering G

    几乎和例题是一样的，不一样之处在于，这道题的边是有权值的。那么，“节点的深度”就要变成“节点到根节点的距离”，其实也没什么大改动，代码就不放了。

其它

  • 一道树上的区间 DP：「NOIP2003 TG」加分二叉树

    这题的突破点在于数的中序遍历必须是 $1,2,3,\ldots,n$，也就是说，一段连续的区间内的节点一定是在一块儿的，而且如果我们选定节点 $i$ 为 $[l,r]$ 这个区间的根节点，那么 $[l,i-1]$ 就是它的左子树，$[i+1,r]$ 就是它的右子树。

    然后三重循环的区间 DP 就来了：令区间 $[l,r]$ 是一棵子树（而不是分散的），在区间范围内枚举这个子树的根节点为 $k$，根据题目给出的公式计算出能得到的最大加分。

    另外，由于枚举时计算左右子树是 $[l,k-1]$ 和 $[k+1,r]$，所有有可能出现左端点比右端点还大的情况，其实这种情况就是空子树。我们可以在初始化的时候把 $dp_{i,i-1}$ 的值设为 $1$ 来解决这个问题。

    输出方案的话，可以用 $f_{i,j}$ 来存把区间 $[i,j]$ 作为一棵子树时的根节点，然后再按照前序遍历的方法“根——左——右”递归输出。

    贴一下代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <cstdio>
    #define rep(i, j, k) for(int i = j; i <= k; ++i)
    #define dep(i, j, k) for(int i = j; i >= k; --i)
      
    int n, p[35], dp[35][35], f[35][35];
      
    void print(int l, int r) {
        if(l > r)
            return;
        printf("%d ", f[l][r]);
        print(l, f[l][r] - 1);
        print(f[l][r] + 1, r);
        return;
    }
      
    int main() {
        scanf("%d", &n);
        rep(i, 1, n)
            scanf("%d", &p[i]);
        rep(i, 1, n)
            dp[i][i] = p[i], f[i][i] = i;
        rep(i, 0, n)
            dp[i + 1][i] = 1;
        rep(len, 2, n) {
            rep(l, 1, n - len + 1) {
                int r = l + len - 1;
                rep(k, l, r) {
                    int w = dp[l][k - 1] * dp[k + 1][r] + p[k];
                    if(w > dp[l][r]) {
                        dp[l][r] = w;
                        f[l][r] = k;
                    }
                }
            }
        }
        printf("%d\n", dp[1][n]);
        print(1, n);
        return 0;
    }