树形 DP & 换根 DP 笔记

一、树形 DP

1. 用途

树形 DP 与普通 DP 的区别，就是普通的 DP 通常是在一个一维数组或二维数组上 DP，但树形 DP 是在一棵树上 DP，解决一些与树形结构有关的问题。

2. 实现方法

(1). 建图

使用链式前向星存图。

(2). 不同用途不同方法

①. 选或不选类

先放一个例题：

平台	网址
洛谷	https://www.luogu.com.cn/problem/P1352

不难看出，上司与下属的关系网是树形结构的，因此，选用树形 DP 解决这道题。

用 $f_{i,0}$ 表示节点 $i$ 不参加舞会，以 $i$ 为根节点的子树的最大值，用 $f_{i,1}$ 表示节点 $i$ 参加舞会，以 $i$ 为根节点的子树的最大值，$f_{i,1}$ 的初始值为题目给出的 $r_i$，设 $u$ 为当前处理边的起点，$v$ 为终点。

由于树形 DP 通常由子节点状态转移得到父节点状态，因此状态转移方程左侧为 $f_{u,x}$。根据题目“隔一代”的参加聚会要求，当 $u$ 不参加聚会时，$v$ 既可以参加聚会，也可以不参加聚会；而当 $u$ 参加聚会时，$v$ 必须不参加聚会。因此可以推出两个状态转移方程：

$$f_{u,0}=f_{u,0}+max(f_{v,0},f_{v,1})$$$$f_{u,1}=f_{u,1}+f_{v,0}$$

树形 DP 部分代码如下：

void dp(int x){
	f[x][0]=0;
	f[x][1]=h[x];
	for(int i=head[x];i;i=edge[i].next){
		int t=edge[i].v;
		dp(t);
		f[x][0]+=max(f[t][0],f[t][1]);
		f[x][1]+=f[t][0];
	}
}

②. 求权值总和/子树大小类

此类树形 DP 多数是前置需要的，难度并不是很高。若用 $f_i$ 来表示节点 $i$ 的子树大小，那么就不难得出下面的状态转移方程：

$$f_u=f_u+f_v+1$$

③.求树的直径类

树的直径，指一棵树里任意两点的最远距离。

如下图所示，这棵树每条路径的长度仍未知，$1$ 是整棵树的根节点，此时，对于以节点 $u$ 为中间点的最长路径，就是在 $u$ 的子树中找两个离 $u$ 距离最远和次远的两个点 $v_1$、$v_2$，在 $f_u$ 存下 $v_1$ 供 $u$ 的父亲节点使用，而答案则用一个变量 $ans=max(ans,v_1+v_2)$ 来保存。

树形 DP 部分的代码如下

inline int dp(int u,int fa){
	int d1=0,d2=0;
	for(int i=head[u];i;i=edge[i].next){
		int j=edge[i].v;
		if(j==fa)continue;
		int t=dp(j,u)+edge[i].len;
		if(t>d1)d2=d1,d1=t;
		else if(t>d2)d2=t;
	}
	ans=max(ans,d1+d2);
	return d1;
}

---

二、换根 DP

1. 用途

换根 DP 由树形 DP 的基础而来，换根 DP 用于解决要枚举一棵树中多个点作为根节点的题，如果进行 $n$ 次树形 DP，时间复杂度就会是 $\mathrm{\Theta }(n^2)$，很多题过不去。但是，如果能够通过状态转移方程，用 $\mathrm{\Theta }(1)$ 的时间将信息从一个根节点的转移到另一个根节点的结果，时间复杂度就是线性的，比较可观

2. 实现方法

(1). 思路

换根 DP 的思路，一般都是先用一个 $g$ 数组来存下子树的信息。如 $g_i$ 则表示以 $i$ 为根的子树的某些信息。处理完之后，从根节点开始，逐步用父亲节点的信息推导出以儿子节点为整棵树的根节点的信息。

(2). 做法

以经典的“求经过每个节点的最长链”的长度为例。

首先任选一点为根，处理出以这个点为根时，从每个点 $u$ 出发，往 $u$ 子树里走的最长路径 $d_{1,u}$ 和次长路径 $d_{2,u}$，结合代码应该很好理解：

void dfs1(int u, int fa) {
    for (auto [v, w] : g[u]) {
        if (v == fa)
            continue;
        dfs1(v, u);
        int dv1 = dp1[v] + w;
        if (dp1[u] <= dv1) {
            dp2[u] = max(dp1[u], dp2[v] + 2 * w);
            dp1[u] = dv1;
            pos[u] = v;
        } else
            dp2[u] = max(dp2[u], dv1);
    }
}

然后考虑换根 dp，经过点 $u$ 的最长路径无非由两种组成可能。

• 由 $d_{1,u}$ 和 $d_{2,u}$ 拼接而成。
• 由 $d_{1,u}$ 和往 $u$ 的父亲走的一条路径拼接而成。

所以，这个问题中，换根 dp 要求的就是往 $u$ 的父亲走的路径的最长值，记作 $f_u$。

• $u$ 是一开始选择的根：$f_u\leftarrow 0$。

• 可以沿着父亲再往父亲走：$f_u\leftarrow f_{fa}+w_{fa\to u}$。

• $fa\to u$ 的路径是 $d_{1,fa}$ 的一部分：$f_u\leftarrow d_{2,fa}+w_{fa\to u}$。因为肯定不能经过 $fa$ 再走回 $d_{1,fa}$ 这条路径。

• 其他情况：$f_u\leftarrow d_{1,fa}+w_{fa\to u}$。

void dfs2(int u, int fa, int fw) {
    if (u == 1)
        up[u] = c[u];
    else {
        up[u] = max(up[fa] + fw, c[u]);
        if (pos[fa] == u) // pos[fa] 就是 fa 的 d1 链指向的第一个节点
            up[u] = max(up[u], dp2[fa] + fw);
        else
            up[u] = max(up[u], dp1[fa] + fw);
    }
    for (auto [v, w] : g[u]) {
        if (v == fa)
            continue;
        dfs2(v, u, w);
    }
}

结合代码也是比较好理解。

三、树上背包的时间复杂度

就是在树上做背包，状态形如 $f_{u,i}$ 表示在 $u$ 点选了 $i$ 个物品，转移形如 $f_{u,i+j}\leftarrow f_{u,i}+f_{v,j}$，其中 $v$ 是 $u$ 子树内任意一点。

一眼看上去 $O(n^3)$，但实际 $O(n^2)$。

证明咕了先。