算法简介：旋风女仆

树形 DP 是一种再树形结构上面跑的 DP ，我们经过有限次的递归统计，记录 DP 值再合并，从而解决问题。

介于树的天生递归结构，我们的树形 DP 也就有这个从父到子从子到父的递推方式。

复杂度一般就是遍历树的复杂度，如果多了维度，那就会乘上那么多。

算法演示：干净利落

例题选讲：骑士团扫除专家

大秦为你打开题目传送门

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。

已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。

一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。

编程任务：

请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。

例题思路：支援就交给我吧

题目就是一棵树，我们就考虑如何去设计状态。这个不难想，由于一个点有几种状态：自己被自己看守，自己被父亲看守，自己被儿子看守。

那就不妨设置状态：

  1. $dp[u][0]$ ：$u$ 号点自己已经有保安时的这个子树的最小经费
  2. $dp[u][1]$ ：$u$ 号点被父亲看守的时候，这个子树的最小经费
  3. $dp[u][2]$ ：$u$ 号点被儿子看守的时候，这个子树的最小经费

那么我们就先来考虑比较简单的被父亲和儿子看守。

如果这个点 $u$ 被父亲看守，那么会是这样的情况：

那么显而易见的，这些 $u$ 的儿子都无人看守，要么他们自己被自己看守，要么自己被他们的儿子看守。

也就是方程 $dp[u][1] = \sum\limits_{v∈son(u)} \min\{dp[v][0], dp[v][2]\}$ 。

那么如果这个点被儿子看守了，会是这样的情况：

其他的儿子，都是没有人看的，也就是说，这时候的价值应该是儿子里面所有 $\min\{dp[v][0], dp[v][2]\}$ 之和再加上某一个儿子放置了一个保安的代价，也就是所有儿子中 $dp[v][0] - \min\{dp[v][0], dp[v][2]\}$ 的最小值。

那么接下来就是这个点放置了保安。先画图看看：

这些儿子，他们既可以自己被自己看，也可以被父亲看，也可以被儿子看，也就是所有儿子这些值的最小值，再加上在当前点 $u$ 放置保安的代价 $a[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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 int128;

namespace FastIO {
	template<typename Tp>
	inline void read(Tp &x) {
		char ch;
		int flag = 0;
		x = 0;
		while(!isdigit(ch = getchar())) if(ch == '-') flag = 1;
		while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
		if(flag) x = -x;
	}
	template<typename Tp , typename ...  Args>
	inline void read(Tp &x, Args & ... x_) {
		read(x);
		read(x_ ... );
	}
};
using namespace FastIO;

const int N = 50010;
const int M = 100010;

struct Edge {
	int to, nt, wt;
	Edge() {}
	Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
};
class Graph {
private :
	Edge e[M];
	int hd[N], cnte;
public :
	inline void AddEdge(int u, int v, int w = 0) {
		e[++cnte] = Edge(v, hd[u], w);
		hd[u] = cnte;
	} 
	inline int head(int u) { return hd[u]; }
	inline int to(int u) { return e[u].to; }
	inline int nt(int u) { return e[u].nt; }
	inline int wt(int u) { return e[u].wt; }
};

int n;
ll a[N];
Graph G;

int fa[N];
ll dp[N][5];

inline void Input() {
	read(n);
//	cout << n << endl;
	int u, m, v;
	for(int i = 1; i <= n; i++) {
//		cout << i << endl;
		read(u);
		read(a[u], m);
//		cout << u << endl;
		for(int j = 1; j <= m; j++) {
			read(v);
//			cout << u << ' ' << v << endl;
			G.AddEdge(u, v);
			fa[v] = u;
		}
	}
//	cout << -1 << endl;
}

inline void Dfs(int u) {
	dp[u][0] = a[u];
	dp[u][1] = 0;
	dp[u][2] = 1e18;
	ll mi = 1e18;
	for(int i = G.head(u); i; i = G.nt(i)) {
		int v = G.to(i);
		Dfs(v);
		dp[u][0] += dp[v][3];
		dp[u][1] += min(dp[v][0], dp[v][2]);
		mi = min(mi, dp[v][0] - min(dp[v][0], dp[v][2]));
	}
	dp[u][2] = dp[u][1] + mi;
	dp[u][3] = min(dp[u][0], min(dp[u][1], dp[u][2]));
}

inline void Work() {
	int rt = 1;
	while(fa[rt]) rt = fa[rt];
	Dfs(rt);
	printf("%lld\n", min(dp[rt][0], dp[rt][2]));
}

int main() {
	int T = 1; 
//	read(T);
	while(T--) {
		Input();
		Work();
	}
	return 0;
}

算法实战：全心全意

查看相关标签喵！