动态规划（树形dp）

（一）、基础

树形$dp$是在树的$dfs$中进行$dp$， 在树形$dp$中，我们动态规划的过程大概就是先递归访问所有子树，再在根上合并，我们求解的往往是所有的在子树范围内的最优解

（二）、例题

1、子树大小

（1）、题意：计算每个点的子树的大小

（2）、题解：

状态表示：$sz[u]$代表$u$为根的子树大小

状态转移：$sz[u]=1+\sum sz[v]$，指本节点的子树大小等于子节点的所有子树大小之和加一

int sz[maxn];
void dfs(int u, int fa)
{
	sz[u] = 1;
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (v != fa)
		{
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2、树的平衡点

（1）、题意： 给你一个有$n$个点的树，求树的平衡点和删除平衡点后最大子树的节点数。平衡点，指的是树中的一个点，删掉该点后使剩下的若干个连通块中最大的连通块的块节点个数最少

（2）、题解：

状态表示：$dp[u]$表示删去节点$i$后最大连通块的块大小

状态转移：$dp[u]=max(n-sz[u],max(sz[v]))$，删去$u$节点后最大的块要么是除去子树$u$的剩下的连通块，要么是节点$u$的子树，其中最大的就是$dp[u]$

int sz[maxn], dp[maxn];
int ans, idx, n;
void dfs(int u, int fa)
{
	sz[u] = 1;
	int maxx = 0;
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (v != fa)
		{
			dfs(v, u);
			sz[u] += sz[v];
			maxx = max(maxx, sz[v]);
		}
	}
	maxx = max(maxx, n - sz[u]);
	if (ans > maxx)
	{
		idx = u;
		ans = maxx;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3、最大独立集

（1）、题意： 有$n$名职员，编号为$1-n$，他们的关系就像一棵以老板为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数$a_i$给出，现在要召开一场周年庆宴会，在保证员工和上司不同时参会的情况下，使得所有参会职员的快乐指数总和最大，求这个最大值

（2）、题解：

状态表示：$dp[u][0]$表示第$u$个员工不参与时的最大值，$dp[u][1]$表示$u$个员工参与时的最大值

状态转移：

$dp[u][0]=\sum max(dp[v][1],dp[v][0])$如果$u$不去参加舞会，则子节点$v$可以参加也可以不参加

$dp[u][1]=a[i]+\sum dp[u][0]$如果$u$参加舞会，则子节点$v$不参加，并且节点$u$加上自身的开心值

vector<int>g[maxn];
int dp[maxn][3];
int a[maxn];
void dfs(int u)
{
	dp[u][0] = 0;
	dp[u][1] = a[u];
	for (int i = 0; i < g[u].size(); i++)
	{
		int v = g[u][i];
		dfs(v);
		dp[u][0] += max(dp[v][0], dp[v][1]);
		dp[u][1] += dp[v][0];
	}
}

ans = max(dp[root][0], dp[root][1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4、最小点覆盖

（1）、题意： 给你一个有$n$个点的树，每两个点之间至多只有一条边。如果在一个结点上放一个士兵，那他能看守与之相连的边，问最少放多少个兵，才能把所有的边能看守住

（2）、题解：

状态表示：

$dp[u][0]$表示在不放士兵并且以$u$为根的子树的每条边都被看住的最小士兵数

$dp[u][1]$表示在放士兵并且以$u$为根的子树的每条边都被看住的最小士兵数

状态转移：

$u$点不放士兵：$dp[u][0]=\sum dp[v][1]$

$u$点放士兵：$dp[u][1]=1+\sum min(dp[v][1],dp[v][0])$

vector<int>g[maxn];
int dp[maxn][3];
void dfs(int u)
{
    dp[u][1] = 1, dp[u][0] = 0;
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        dfs(v);
        dp[u][1] += min(dp[v][0], dp[v][1]);
        dp[u][0] += dp[v][1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5、最小支配集

（1）、题意： 给你一个有$n$个点的树，每两个点之间至多只有一条边。如果在第$i$个点部署信号塔，就可以让它和所有与它相连的点都收到信号。求最少部署多少个信号塔能让所有点都能收到信号

（2）、题解：注意一个点是否选择不仅会影响儿子还会影响父亲的选择

状态表示：

$dp[u][0]$ 表示选点$u$，且以$u$为根的子树每个点都被覆盖的最少信号塔部署数量

$dp[u][1]$ 表示不选点$u$，并且$u$被儿子覆盖的最少信号塔部署数量

$dp[u][2]$表示不选点$u$，但是$u$没被儿子覆盖，且以$u$为根的子树的其他点都被覆盖的最少信号塔部署数量，也就是说此时需要选择$u$的父亲来覆盖$u$

状态转移：

$dp[u][0]=1+\sum min(f[v][0],f[v][1],f[v][2])$，选择$u$点后，儿子节点可选可不选

$dp[u][2]=\sum min(f[v][0],f[v][1])$ 当我们不选点$u$，并且$v$未被覆盖的时候，它的儿子们都至少被覆盖或者不选

当我们不选点$u$，并且$u$被覆盖的时候，且有$dp[v][0]\le dp[v][1]$，这是我们选了$u$点不会更恶劣，故我们选择$u$，此时$dp[u][1]=\sum min(f[v][0],f[v][1])$；如果不存在这样一个儿子，那么我们就需要选择一个损失最小的，此时$dp[u][1]=\sum min(f[v][0],f[v][1])+min(dp[v][0]-dp[v][1])$

int dp[maxn][4];
void dfs(int u, int fa)
{
	dp[u][0] = 1, dp[u][1] = dp[u][2] = 0;
	int tmp = inf;
	bool flag = 1;
	for (int i = 0; i < g[u].size(); ++i)
	{
		int v = g[u][i];
		if (v == fa)
			continue;
		dfs(v, u);
		dp[u][2] += min(dp[v][1], dp[v][0]);
		dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
		if (dp[v][0] <= dp[v][1])
		{
			flag = 0;
			dp[u][1] += dp[v][0];
		}
		else
		{
			dp[u][1] += dp[v][1];
			tmp = min(tmp, dp[v][0] - dp[v][1]);
		}
	}
	if (flag)
		dp[u][1] += tmp;
}
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

另一种做法：

int over[maxn], ans;
void dfs(int u, int fa)
{
	bool flag = 0;
	for (int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i];
		if (v != fa)
		{
			dfs(v, u);
			flag |= over[v];
		}
	}
	if (!flag && !over[u] && !over[fa])	//如果u本身、儿子、父亲节点都没遍历过
	{
		over[fa] = 1;
		ans += 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

6、树形背包

（1）、题意：有$n$个物品和一个承重是$m$的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。求解$m$承重下能装下的最大价值

（2）、题解：第一维枚举子树，第二维枚举容量，第三维枚举决策（即给子树分配多少重量）

状态表示：$dp[u][i]$代表在以$u$为子树的点上选择物品，在承重不超过$i$时能获得的最大价值

状态转移：$dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[v][j])$

vector<int>g[maxn];
int n, m;
int weight[maxn], val[maxn];
void dfs(int u)
{
	for (int i = weight[u]; i <= m; i++)
		dp[u][i] = val[u];	//由于只有选择了根节点，才会继续往下遍历，故根节点先选上
	for (auto v : g[u])
	{
		dfs(v);
		for (int i = m; i >= weight[u]; i--)  //剩余重量小于根节点总重量则不可能取
		{
			for (int j = 0; j <= i - weight[u]; j++) //分给子树重量j后剩余不能小于weight[u]
			{
				dp[u][i] = max(dp[u][i], dp[u][i - j] + dp[v][j]);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7、二叉苹果树（树形背包）

（1）、题意： 给定一棵$n$个点二叉树，每条边有边权$a_i$，保留$m$条的边，使得保留下来的边的边权和最大

（2）、题解：本题类似树形背包，但区别在于点和边

状态表示：$dp[u][i]$代表在以$u$为子树中选择边，在容量不超过$i$时能获得的最大价值

状态转移：$dp[u][i]=max(dp[u][i],dp[u][i-j-1]+dp[v][j]+w[i])$

void dfs(int u)
{
	for (auto node : g[u])
	{
		int v = node.first;
		int w = node.second;
		dfs(v);
		for (int i = m; i >= 1; i--)
		{
			for (int j = 0; j <= i - 1; j++)
			{
				dp[u][i] = max(dp[u][i], dp[u][i - j - 1] + dp[v][j] + w);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8、树的直径（详见图论）

9、$STA-Station$

（1）、题意： 给定一个$n$个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大

（2）、题解：树形$dp$中的换根$dp$问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。通常需要两次$dfs$，第一次$dfs$处理诸如深度，点权和之类的信息，在第二次$dfs$开始进行换根$dp$

对于本题我们可以先从任意一点出发求出该节点的$ans$，然后进行换根$dp$，求出每个点对应的$ans$

状态表示：$dp[u]$表示以$u$为根，所有的节点深度之和

状态转移：$dp[v]=dp[u]-sz[v]+(n-sz[v])$

ll dp[maxn];
vector<int>g[maxn];
int n;
ll deep[maxn], sz[maxn];
void dfs1(int u, int fa)
{
	sz[u] = 1;
	deep[u] = deep[fa] + 1;
	for (auto v : g[u])
	{
		if (v != fa)
		{
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}
}
void dfs2(int u, int fa)
{
	for (auto v : g[u])
	{
		if (v != fa)
		{
			dp[v] = dp[u] - sz[v] + (n - sz[v]);
			dfs2(v, u);
		}
	}
}
void solve()
{
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1, 0);
	for (int i = 1; i <= n; i++)
	{
		dp[1] += deep[i];
	}
	dfs2(1, 0);
	int idx = 1;
	for (int i = 1; i <= n; i++)
	{
		if (dp[idx] < dp[i])
			idx = i;
	}
	cout << idx << '\n';
}
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

10、道路反转

（1）、题意：一个国家有$n$个城市，这个国家一共有$n-1$条连接两个城市的单向通道。现在需要选择一个首都，并且这座城市可以通往其他任意城市，但为了满足这个要求，可能需要对某些通道进行逆转。问如何选择首都，可以使得需要逆转的通道数量最少

（2）、题解：我们可以先从任意一点求出需要反转的道路：建双向边，不需要反转边权为0，需要反转边权为1；然后我们进行换根$dp$求出每个点的$ans$

状态表示：$dp[u]$表示以$u$城市为首都需要反转的道路

状态转移：

如果该道路需要反转，则对于儿子节点来说不需要反转$dp[v]=dp[u]-1$

如果该道路不需要反转，则对于儿子节点来说需要反转$dp[v]=dp[u]+1$

int dp[maxn];
int to[maxn << 1], nex[maxn << 1], w[maxn << 1], head[maxn], cnt;
int cost[maxn];
void add(int u, int v, int we)
{
	to[++cnt] = v;
	w[cnt] = we;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void dfs1(int u, int fa)
{
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (v != fa)
		{
			dfs1(v, u);
			cost[u] += cost[v] + w[i];
		}
	}
}
void dfs2(int u, int fa)
{
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (v != fa)
		{
			if (w[i])
				dp[v] = dp[u] - 1;
			else
				dp[v] = dp[u] + 1;
			dfs2(v, u);
		}
	}
}
void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		add(u, v, 0);
		add(v, u, 1);
	}
	dfs1(1, 0);
	dp[1] = cost[1];
	dfs2(1, 0);
	int minv = inf;
	for (int i = 1; i <= n; i++)
	{
		minv = min(minv, dp[i]);
	}
	cout << minv << '\n';
	for (int i = 1; i <= n; i++)
	{
		if (dp[i] == minv)
		{
			cout << i << ' ';
		}
	}
}
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