树形dp，顾名思义，给出一棵树并对其赋予权值（或边权或点权），在树上进行动态规划。
其基本思路是从根节点开始进行记忆化搜索，或是从叶子节点开始自下而上正向推进。
题目中要求所有度为1的点都不能到达关键点(S)，那么问题可以转述成“对于一棵以(S)点位根节点的树，所有的叶子节点都不能到达根(S)，这边给出一个棵树：
在这张图中，假设关键点为(1)，那么我需要保证(2,4,5)这三个点无法到达(1)，对于(4,5)两个点而言，我可以选择删去(1->3)这条边，也可以分别删去(3->4)和(3->5)两条边。
由此可以得出状态转移方程(f[i]=max{f[j]})，如果为叶子节点，返回该节点与其父节点的边权。
有关存图与搜索的方式可以分为以下两种。
(1) 如果父子关系明确，可以采用有向图的方式存邻接表。
(2) 对于任意树，都可以采用无向图的方式存邻接表，在搜索时记录该节点的父节点防止走回头路。
#include <bits/stdc++.h> #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define ll long long #define pb push_back using namespace std; const int maxn = 1e5 + 10; const ll INF = 1e18; int n, m, s; vector<int> v[maxn]; map<pair<int, int>, ll> mp; ll f[maxn]; ll dfs(int x, int fa) { if (v[x].size() == 1 && x != s) return mp[make_pair(x, fa)]; for (int i = 0; i < v[x].size(); i++) { if (v[x][i] == fa) continue; f[x] += dfs(v[x][i], x); } if (fa == 0) return f[x]; return f[x] = min(f[x], mp[make_pair(x, fa)]); } int main() { fast; cin >> n >> m >> s; int uu, vv, w; for (int i = 1; i <= m; i++) { cin >> uu >> vv >> w; v[uu].pb(vv); v[vv].pb(uu); mp[make_pair(uu, vv)] = w; mp[make_pair(vv, uu)] = w; } for (int i = 1; i <= n; i++) { f[i] = 0; } cout << dfs(s, 0) << ' '; }
题目相当的直接，找出权值最大的子链。
最关键的地方在于子链的定义。
仍然是这一棵树，(1->3->5)固然是一条子链，然而如同(4->3->5)，(2->1->3->5)这类也算作子链。在状态转移时，我们转移以该节点为根的情况下子链权值的最大值，对于每个节点，找到权值最大的两条子链并将权值相加。
#include <bits/stdc++.h> #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define ll long long #define pb push_back using namespace std; const int maxn = 1e5 + 10; int n; ll a[maxn]; ll dp[maxn] = {0}; ll maxx = -1e9; vector<int> v[maxn]; void dfs(int x, int pre) { dp[x] = a[x]; for (int i = 0; i < v[x].size(); i++) { if (v[x][i] == pre) continue; dfs(v[x][i], x); maxx = max(maxx, dp[x] + dp[v[x][i]]); dp[x] = max(dp[x], dp[v[x][i]] + a[x]); } maxx = max(maxx, dp[x]); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { int p, q; cin >> p >> q; v[p].pb(q); v[q].pb(p); } dfs(1, 0); cout << maxx << ' '; }
再把这个图复制下来：
对于节点(3)，它的子树包括({4})，({5})，({1,2})，我们可以从任意点作为根节点进行搜索，在这棵根确定的树中，对于任意一点(x)，不仅需要考虑子树，还需要向上考虑剩余的节点数量（因为当(x)作为根节点是，这些剩下的点也将成为一棵子树）。
在状态转移时，用(f[x])表示以该节点为根的子树的节点数，那么( -f[x])就是剩余部分的节点数，找到其中的最小值即可（节点数越小，越平衡）。
#include <bits/stdc++.h> #define ll long long #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define pb push_back using namespace std; const int maxn = 1010; vector<int> v[maxn]; int dp[maxn]; int ansx = 1e9, ansnum = 1e9; int n; void dfs(int x, int pre) { dp[x] = 1; int m = 0; for (int i = 0; i < v[x].size(); i++) { if (v[x][i] == pre) continue; dfs(v[x][i], x); dp[x] += dp[v[x][i]]; m = max(m, dp[v[x][i]]); } m = max(m, n - dp[x]); if (m < ansnum) { ansnum = m; ansx = x; } else if (m == ansnum) { if (ansx > x) ansx = x; } } int main() { fast; cin >> n; int p, q; for (int i = 1; i < n; i++) { cin >> p >> q; v[p].pb(q); v[q].pb(p); } dfs(1, 0); cout << ansx << ' ' << ansnum << ' '; }
NC51178（最大独立集）
状态转移思路差别不大，只是对于一个节点，需要和他孩子的孩子建立关系。因为上面的所有题目都是父子关系，所以不需要进行记忆化搜索，但这里对于每个点，都有可能被搜索到两次，所以要用到记忆化搜索。
#include <bits/stdc++.h> #define ll long long #define pb push_back #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 6010; ll h[maxn]; int vis[maxn]; ll f[maxn]; vector<int> mp[maxn]; ll dfs(int x) { if (f[x]) return f[x]; ll tmp1 = 0; ll tmp2 = 0; for (int i = 0; i < mp[x].size(); i++) { int nex = mp[x][i]; tmp2 += dfs(mp[x][i]); for (int j = 0; j < mp[nex].size(); j++) { tmp1 += dfs(mp[nex][j]); } } return f[x] = max(tmp1 + h[x], tmp2); } int main() { fast; int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i]; } int u, v; for (int i = 1; i < n; i++) { cin >> u >> v; vis[u]++; mp[v].pb(u); } cin >> u >> v; for (int i = 1; i <= n; i++) { f[i] = 0; } for (int i = 1; i <= n; i++) { if (!vis[i]) dfs(i), cout << f[i] << ' '; } }
NC24953（最小支配集）
最小支配集含义为当树中一个点被选中时，其直接相连的点都视为被选中，问这棵树最少需要多少个点可以将所有点全部选中。
一个点被选中有三种情况：
(1) 当前点被直接选中
(2) 其子节点被选中
(3) 其父节点被选中
那么我们就用(f[i][j])表示第(i)个点的三种情况下最小的结果。（三种情况分别对应(j)取(0,1,2)）
对于(1)，直接找到子节点三种情况的最小值相加即可。
对于(3)，只要考虑子节点(1)(2)两种情况的最小值相加即可。
情况(2)相对复杂，该情况下，其子节点至少有一个被选中，但最优情况下可能不会被选中，因此需要考虑：
1. 如果某个子节点选中时情况最优，直接选择，且不需要后续操作
2. 若均为选中子节点的子节点情况最优，然而现在要求必须要选上一个子节点，所以需要补上差值(min(f[u][0]-f[u][1]))。
最终的结果为(min(f[1][0],f[1][1]))，没有(f[1][2])。（骂自己）
#include <bits/stdc++.h> #define ll long long #define pb push_back #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 10010; const int INF = 0x3f3f3f3f; vector<int> edge[maxn]; int f[maxn][3]; int n; void dfs(int u, int fa) { int flag = 1; int tmp = INF; f[u][0] = 1; f[u][1] = 0; f[u][2] = 0; for (int v : edge[u]) { if (v == fa) continue; dfs(v, u); f[u][0] += min({f[v][0], f[v][1], f[v][2]}); f[u][2] += min(f[v][0], f[v][1]); if (f[v][0] <= f[v][1]) { flag = 0; f[u][1] += f[v][0]; } else { f[u][1] += f[v][1]; tmp = min(tmp, f[v][0] - f[v][1]); } } if (flag) f[u][1] += tmp; } int main() { cin >> n; int u, v; for (int i = 1; i < n; i++) { cin >> u >> v; edge[u].pb(v); edge[v].pb(u); } dfs(1, 0); cout << min(f[1][0], f[1][1]) << ' '; }