记录树形dp的常见考法与需要注意的细节，目前包含树的直径与中心，树上背包，父子结点选择限制型dp，二次扫描与换根。

树形dp

概述

dp在树形结构上的实现。

一般使用记忆化搜索实现，dp的计算与dfs记忆化保证拓扑序是分开的，所以dfs的时候不需要传递dp的状态参数（但是阶段肯定是要传的）。

树结构上想不到做法的时候，可以考虑退化成链的情况。

常见考法与细节

树的直径

最简单的做法就是两次dfs，找最远点，之前已经比较熟悉了。

除此之外还有一个树形dp的做法。我们考虑每个结点，把它想象成一个钉子，路径想象成绳子，然后把路径挂在这个钉子上，则挂的路径的最长距离就是这个结点往下走的最大距离以及次大距离之和。根据这个特点，只要在dfs的时候自底向上维护往下走的最大值和次大值，就可以计算出每个点的挂在这个点上的路径的最大值，最后对所有点的这个最大值取max就是树的直径的长度。

参考代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

typedef long long ll;

typedef struct {
    ll to, nxt, w;
} Edge;

Edge edge[2 * N];
ll head[N], cnt, n;
ll ans = 0;

void add(ll x, ll y, ll z) {
    edge[cnt].to = y;
    edge[cnt].nxt = head[x];
    edge[cnt].w = z;
    head[x] = cnt++;
}   

ll dfs(ll u, ll fa) {
    // d1为最大，d2为次大
    ll dist = 0, d1 = 0, d2 = 0;

    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        if (edge[i].to != fa) {
            ll d = dfs(edge[i].to, u) + edge[i].w;
            dist = max(dist, d);
            if (d >= d1) {
                d2 = d1;
                d1 = d;
            } else if (d > d2) {
                d2 = d;
            } 
        }
    }

    ans = max(ans, d1 + d2);
    return dist;
}

int main() {
    ll x, y, z;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
    }
    for (int i = 1; i < n; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }

    dfs(1, 0);

    printf("%lld\n", ans);
    return 0;
}

如果想要具体知道直径上究竟有哪些点，一个可行的方法是在维护往下走的最大和次大值的同时，维护二者的结点。

父结点更新子结点

有时候树形dp更新时使用父结点更新子结点的，有时候父子会互相更新不同的信息。在这种情况下，一般就是自底向上做一次dfs，自顶向下做一次dfs，才能计算出所有的信息。

比较典型的例子就是求出某棵树中到所有点的最大距离最小的那个点的最大距离，除了直接拿树的直径”中点“硬莽，还可以使用树形dp。

我们考虑维护每个结点的到其他结点的最大值，这个值的计算还需要其他一些辅助的信息，比如我们可以通过每个结点往下走的最长路以及往上走的最长路这两个信息来更新最大距离，而对于往上走的最长路，又得考虑其父亲结点的往下或者往上走的最长路，故结点u到其他结点的最大距离由以下几个部分组成：

• u往下走的最大距离
• u往上走的最大距离
  • u到父亲fa的距离加上fa往上走的最大距离
  • u到父亲fa的距离加上fa往下走且不经过u的最大距离
    • fa往下走最大距离的方案经过u，则取次大距离
    • 否则取最大距离

对于第一部分，类似于求树的直径的dp做法即可计算，对于第二部分，需要从父亲转移到儿子，且要用到第一次dp的结果，所以只能做两次更新方向不同的dp。从上往下推也没什么特别的，只是之前一直都没太注意过而已。话说，二次扫描与换根法就需要我们用父亲结点更新子节点。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;
const int INF = 1e9;

typedef long long ll;

typedef struct {
    ll to, nxt, w;
} Edge;

Edge edge[2 * N];
ll head[N], cnt, n;
ll d1[N], d2[N], up[N], p1[N], p2[N];

void add(ll x, ll y, ll z) {
    edge[cnt].to = y;
    edge[cnt].nxt = head[x];
    edge[cnt].w = z;
    head[x] = cnt++;
}   

ll dfs_d(ll u, ll fa) {
    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        if (edge[i].to != fa) {
            ll d = dfs_d(edge[i].to, u) + edge[i].w;
            if (d >= d1[u]) {
                d2[u] = d1[u];
                p2[u] = p1[u];
                d1[u] = d;
                p1[u] = edge[i].to;
            } else if (d > d2[u]) {
                d2[u] = d;
                p2[u] = edge[i].to;
            }
        }
    }

    return d1[u];
}

void dfs_u(ll u, ll fa) {
    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        if (edge[i].to != fa) {
            int j = edge[i].to;
            if (p1[u] != j) {
                up[j] = max(up[u], d1[u]) + edge[i].w;
            } else {
                up[j] = max(up[u], d2[u]) + edge[i].w;
            }
            dfs_u(j, u);
        }
    }
}

int main() {
    ll x, y, z;
    scanf("%lld", &n);
    memset(head, -1, sizeof head);
    for (int i = 1; i < n; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }

    dfs_d(1, 0);
    dfs_u(1, 0);

    ll res = INF;
    for (int i = 1; i <= n; i++) {
        res = min(res, max(up[i], d1[i]));
    }

    printf("%lld\n", res);
    return 0;
}

树上背包

体现为在树上选择一个连通块（对于树上的一个连通块，块内的所有点的LCA也在这些点当中），使得最大/最小化某个属性等。

在设计状态的时候，为了保证连通，所以dp[u][j]表示在u为根的子树中选择容量不超过j，且u必选的balabala。需要初始化一下dp[u][volume(u)]或者在转移的时候特殊处理一下。

在转移的时候，用到的前置知识是分组背包，相关注意事项见笔记《背包dp》

给出一道模板题：有一棵无向带权树，从中选择一个大小为m的连通块，必选结点1，使得连通块所有边的边权之和最大。

代码模板如下：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

typedef struct {
    int to, nxt, w;
} Edge;

Edge edge[2 * N];
int n, m, cnt, head[N], dp[N][N];

void add(int x, int y, int z) {
    edge[cnt].to = y;
    edge[cnt].nxt = head[x];
    edge[cnt].w = z;
    head[x] = cnt++;
}

void dfs(int u, int fa) {
    for (int i = head[u]; i >= 0; i = edge[i].nxt) {
        if (edge[i].to != fa) {
            dfs(edge[i].to, u);

            for (int j = m; j >= 0; j--) {
                for (int k = 0; k < j; k++) {
                    dp[u][j] = max(dp[u][j],
                                   dp[edge[i].to][k] + dp[u][j - k - 1] + edge[i].w);
                }
            }
        }
    }
} 

int main() {
    int x, y, z;
    cin >> n >> m;

    memset(head, -1, sizeof head);

    for (int i = 1; i < n; i++) {
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }

    dfs(1, 0);

    printf("%d\n", dp[1][m]);
    return 0;
}

父子结点选择限制型dp

典型代表就是没有上司的舞会。除了该题中的父子结点不能同时出现的情况，可能还会有父子结点至少得出现一个，或者其他更复杂的关系。对于此类问题，可以按照选与不选本结点来设计状态。对于更复杂的关系，可能要根据本结点的父亲或者儿子的选法设计更加细致的状态（状态机dp！）分情况讨论转移。

二次扫描与换根法

这个技巧一般用在需要使用常数次dfs去统计所有点的某个信息/以每个结点为根时的所有信息。

比如最经典的，求树上一个点，使得以这个点为根的树的各个结点深度之和最大，$n = 1e6$。

可以注意到，以$u$为根和以$u$的亲儿子$v$为根时，计算的结果有很多是可以重用的：

• 原来以$v$为根的子树中的所有节点，相对于以$u$为根的树，在以$v$为根的时候，这$size[v]$个结点的深度全部都减一
• 除此之外的$n - size[v]$个结点，深度都加一

所以设$dp[u]$为以$u$为根的树的深度之和，那么$dp[v] = dp[u] - size[v] + n - size[v]$

预处理出以某个结点为根的树深度之和以及子树大小即可。

参考代码实现：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 9;

typedef struct {
    int to, ne;
} Edge;

typedef long long ll;

Edge edge[2 * N];
ll dp[N], head[N], cnt, n, d[N], sz[N];

void add(ll x, ll y) {
    edge[cnt].to = y;
    edge[cnt].ne = head[x];
    head[x] = cnt++;
}

ll read() {
    char ch = getchar();
    ll f = 1, v = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f *= -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        v = 10 * v + ch - '0';
        ch = getchar();
    }
    return v * f;
}

void dfs1(ll u, ll fa, ll depth) {
    d[u] = depth;
    dp[1] += d[u];
    sz[u]++;
    
    for (int i = head[u]; i >= 0; i = edge[i].ne) {
        int j = edge[i].to;
        if (j != fa) {
            dfs1(j, u, depth + 1);
            sz[u] += sz[j];
        }
    }
}

void dfs2(ll u, ll fa) {
    for (int i = head[u]; i >= 0; i = edge[i].ne) {
        int v = edge[i].to;
        if (v != fa) {
            dp[v] = dp[u] + n - 2 * sz[v];
            dfs2(v, u);
        }
    }
}

int main() {
    n = read();
    
    ll x, y;
    memset(head, -1, sizeof head);
    for (int i = 1; i < n; i++) {
        x = read();
        y = read();
        add(x, y);
        add(y, x);
    }
    
    dfs1(1, 0, 0);
    dfs2(1, 0);
    
    ll ans = 0, maxd = 0;
    for (int i = 1; i <= n ; i++) {
        if (dp[i] > maxd) {
            maxd = dp[i];
            ans = i;
        }
    }
    
    printf("%lld\n", ans);
    
    return 0;
}

可以看出，之所以叫二次扫描，是因为需要一次预处理，先把以某个结点为根的所有信息算出来。

之所以叫换根法，是因为我们第二次扫描的时候基于父子关系与预处理的结果快速计算以儿子为根时的信息。