经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C++ » 查看文章
树形DP + 换根DP
来源：cnblogs　　作者：SunnyYuan　　时间：2023/7/28 10:17:19　　对本文有异议

树形DP——基础

P1352 没有上司的舞会

设 \(f[i][0/1]\) 表示第 \(i\) 个人不去或者去。

如果第 \(i\) 个人没去，那么下属可去可不去，所以 \(f[i][0] = \sum max\{f[j][0],f[j][1]\}\)，\(j\) 为 \(i\) 的子节点。

如果第 \(i\) 个人去了，那么下属不能去，所以 \(f[i][1] = a[i] + \sum f[j][0]\)，\(j\) 为 \(i\) 的子节点。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cmath>
  6. using namespace std;
  8. const int N = 6010;
  10. struct Edge {
  11. 	int to, next;
  12. }e[N * 2];
  14. int head[N], idx;
  16. void add(int a, int b) {
  17. 	idx++, e[idx].to = b, e[idx].next = head[a], head[a] = idx;
  18. }
  20. int n;
  21. int a[N];
  22. int f[N][2];
  24. void dfs(int u, int fa) {
  25. 	f[u][1] = a[u];
  26. 	for (int i = head[u]; i; i = e[i].next) {
  27. 		int to = e[i].to;
  28. 		if (to == fa) continue;
  29. 		dfs(to, u);
  30. 		f[u][1] += f[to][0];
  31. 		f[u][0] += max(f[to][0], f[to][1]);
  32. 	}
  33. }
  35. int main() {
  36. 	ios::sync_with_stdio(false);
  37. 	cin.tie(nullptr);
  39. 	cin >> n;
  40. 	for (int i = 1; i <= n; i++) cin >> a[i];
  41. 	for (int i = 1; i < n; i++) {
  42. 		int a, b;
  43. 		cin >> a >> b;
  44. 		add(a, b);
  45. 		add(b, a);
  46. 	}
  47. 	dfs(1, 0);
  48. 	cout << max(f[1][0], f[1][1]) << '\n';
  49. 	return 0;
  50. }

POJ 1463 / UVA1292 Strategic game

与上一题类似，

设 \(f[i][0/1]\) 表示第 \(i\) 个人是否驻守。

如果第 \(i\) 个人没去，那么它的儿子必须驻守，所以 \(f[i][0] = 1 + \sum f[j][1]\)，\(j\) 为 \(i\) 的子节点。

如果第 \(i\) 个人去了，那么它的儿子可去可不去，所以 \(f[i][1] = \sum min\{f[j][0],f[j][1]\}\)，\(j\) 为 \(i\) 的子节点。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 1510;
  9. struct Edge {
  10. 	int to, next;
  11. }e[N * 2];
  13. int head[N], idx;
  15. void add(int a, int b) {
  16. 	idx++, e[idx].to = b, e[idx].next = head[a], head[a] = idx;
  17. }
  19. int n;
  20. int f[N][2];
  22. void dfs(int u, int fa) {
  23. 	f[u][1] = 1;
  24. 	for (int i = head[u]; i; i = e[i].next) {
  25. 		int to = e[i].to;
  26. 		if (to == fa) continue;
  27. 		dfs(to, u);
  28. 		f[u][0] += f[to][1];
  29. 		f[u][1] += min(f[to][0], f[to][1]);
  30. 	}
  31. }
  33. void solve() {
  34. 	memset(f, 0, sizeof(f));
  35. 	memset(head, 0, sizeof(head));
  36. 	idx = 0;
  37. 	for (int i = 1; i <= n; i++) {
  38. 		int a, num;
  39. 		scanf("%d:(%d)", &a, &num);
  40. 		a++;
  41. 		for (int j = 1; j <= num; j++) {
  42. 			int b;
  43. 			scanf("%d", &b);
  44. 			b++;
  45. 			add(a, b);
  46. 			add(b, a);
  47. 		}
  48. 	}
  49. 	dfs(1, 0);
  50. 	printf("%d\n", min(f[1][0], f[1][1]));
  51. }
  53. int main() {
  54. 	while (~scanf("%d", &n)) solve();
  55. 	return 0;
  56. }

P3574 [POI2014] FAR-FarmCraft

设 \(f[i]\) 表示以 \(i\) 为根节点的子树中（包括节点 \(i\)）的所有人安装好游戏所需要的时间（与下面的 \(g[i]\) 并没有包含关系，管理员也没有强制性要求要回到根节点，比如会出现下图情况）。

设 \(g[i]\) 表示从 \(i\) 开始往下走，兜一圈又回到 \(i\) 所需要的时间。

实际上 \(f[i]\) 可能 \(< g[i]\)，比如当出现如下情况的时候：

image

那我们先访问那个节点呢？

分为两种情况考虑，即 \(f[i] - g[i] \geq 0\) 和 \(f[i] - g[i] < 0\) 两种情况。

如果管理员回到了起点那些人还没有装完（即 \(f[i] - g[i] \geq 0\)），那么就需要等待 \(f[i] - g[i]\) 的时间所有人才能安装好。

根据常识，在等待的这段时间我们可以去下一家，以减少所需的总时间。

这里我们利用贪心，让需要等待时间最久的作为第一个访问的节点，

这样可以管理员在他漫长的安装时间内将电脑送给其他人。

而如果出现了像上图一样的情况（即 \(f[i] - g[i] < 0\)） 的情况，

根本就不需要等待，

也就不用排序，

随机访问即可，

但为了简单起见，

排了序也没有什么问题。

所以我们可以对 \(f[i] - g[i]\) 从大到小进行排序。

再挨个访问即可。

然后就是利用 \(f\) 和 \(g\) 来用子树信息更新父亲节点。

如下图：

image

先说结论：只安装到 \(i\) 点会需要 \(\sum (g[j] + 2) + 1 + f[i]\) 的时间能完成安装，其中 \(j\) 为比 \(i\) 先遍历到的同一层的节点（如上图）。

为什么是这样呢？

第一部分的 \(\sum (g[j] + 2)\) 表示遍历完所有 \(j\) 子树的节点，每次都回到根节点（所以要 \(+2\)）。

第二部分的 \(+1\) 表示从根节点走到 \(i\) 所需要的步骤（即为 \(1\) 步）。

最后一部分的 \(f[i]\) 表示把 \(i\) 子树内所有的游戏装好了需要花的时间。

总时间取 \(\max\) 即可， 即 \(f[root] = \max\{\sum (g[j] + 2) + f[i] + 1\}\)。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  6. using namespace std;
  8. const int N = 500010;
  10. struct Edge {
  11. 	int to, next;
  12. }e[N * 2];
  14. int head[N], idx;
  16. void add(int a, int b) {
  17. 	idx++;
  18. 	e[idx].to = b;
  19. 	e[idx].next = head[a];
  20. 	head[a] = idx;
  21. }
  23. int n, t[N];
  24. int f[N], g[N];
  26. void dfs(int u, int fa) {
  27. 	vector<int> wait;
  28. 	for (int i = head[u]; i; i = e[i].next) {
  29. 		int to = e[i].to;
  30. 		if (to == fa) continue;
  31. 		dfs(to, u);
  32. 		wait.push_back(to);
  33. 	}
  34. 	sort(wait.begin(), wait.end(), [](const int& a, const int& b) { return f[a] - g[a] > f[b] - g[b]; });
  35. 	for (int i = 0; i < wait.size(); i++) {
  36. 		f[u] = max(f[u], g[u] + 1 + f[wait[i]]);
  37. 		g[u] += g[wait[i]] + 2;
  38. 	}
  39. 	if (t[u] > g[u] && u != 1) f[u] = max(f[u], t[u]);
  40. }
  42. int main() {
  43. 	ios::sync_with_stdio(false);
  44. 	cin.tie(nullptr);
  46. 	cin >> n;
  47. 	for (int i = 1; i <= n; i++) cin >> t[i];
  48. 	for (int i = 1; i < n; i++) {
  49. 		int a, b;
  50. 		cin >> a >> b;
  51. 		add(a, b);
  52. 		add(b, a);
  53. 	}
  54. 	dfs(1, 0);
  55. 	cout << max(f[1], g[1] + t[1]) << '\n';
  56. 	return 0;
  57. }

树形DP——树上背包

P2014 CTSC1997 选课

不难发现这是个树结构。

课程相当于树上的每一个节点，

学分相当于权值。

设 \(f[i][j][k]\) 表示遍历到第 \(i\) 棵子树的第 \(j\) 个元素并且选择 \(k\) 个节点可以得到的最大权值。

\(f[cur][i][j] = \max \{f[cur][i - 1][j - l] + f[ver[cur][i]][size[ver[i]]][l]\}\)。

其中 \(ver[i][j]\) 表示 \(i\) 节点的第 \(j\) 个子节点，\(size[x]\) 表示以 \(x\) 为根节点的子树的大小。

然后像01背包一样把第二维滚掉就可以了。

C++代码

版本1：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 310;
  9. struct Edge {
  10. 	int to, next;
  11. }e[N * 2];
  13. int head[N], idx;
  15. void add(int a, int b) {
  16. 	idx++;
  17. 	e[idx].to = b;
  18. 	e[idx].next = head[a];
  19. 	head[a] = idx;
  20. }
  22. int n, m;
  23. int sz[N];
  24. int a[N];
  25. int f[N][N];
  27. void dfs(int u) {
  28. 	sz[u] = 1;
  29. 	f[u][1] = a[u];
  30. 	for (int i = head[u]; i; i = e[i].next) {
  31. 		int to = e[i].to;
  32. 		dfs(to);
  33. 		sz[u] += sz[to];
  34. 		for (int j = min(sz[u], m + 1); j >= 1; j--) {
  35. 			for (int k = 1; k <= min(sz[to], j - 1); k++) {
  36. 				f[u][j] = max(f[u][j], f[u][j - k] + f[to][k]);
  37. 			}
  38. 		}
  39. 	}
  40. }
  42. int main() {
  43. 	ios::sync_with_stdio(false);
  44. 	cin.tie(nullptr);
  46. 	cin >> n >> m;
  47. 	for (int i = 1; i <= n; i++) {
  48. 		int b;
  49. 		cin >> b >> a[i];
  50. 		add(b, i);
  51. 	}
  53. 	dfs(0);
  54. 	cout << f[0][m + 1] << '\n';
  55. 	return 0;
  56. }

版本2：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 310;
  9. struct Edge {
  10. 	int to, next;
  11. }e[N * 2];
  13. int head[N], idx;
  15. void add(int a, int b) {
  16. 	idx++;
  17. 	e[idx].to = b;
  18. 	e[idx].next = head[a];
  19. 	head[a] = idx;
  20. }
  22. int n, m;
  23. int sz[N];
  24. int a[N];
  25. int f[N][N];
  27. void dfs(int u) {
  28. 	sz[u] = 1;
  29. 	f[u][1] = a[u];
  30. 	for (int i = head[u]; i; i = e[i].next) {
  31. 		int to = e[i].to;
  32. 		dfs(to);
  33. 		for (int j = min(sz[u], m + 1); j >= 1; j--) {
  34. 			for (int k = 1; k <= sz[to] && j + k <= m + 1; k++) {
  35. 				f[u][j + k] = max(f[u][j + k], f[u][j] + f[to][k]);
  36. 			}
  37. 		}
  38. 		sz[u] += sz[to];
  39. 	}
  40. }
  42. int main() {
  43. 	ios::sync_with_stdio(false);
  44. 	cin.tie(nullptr);
  46. 	cin >> n >> m;
  47. 	for (int i = 1; i <= n; i++) {
  48. 		int b;
  49. 		cin >> b >> a[i];
  50. 		add(b, i);
  51. 	}
  53. 	dfs(0);
  54. 	cout << f[0][m + 1] << '\n';
  55. 	return 0;
  56. }

P4516 [JSOI2018] 潜入行动

设 \(f[i][j][0/1][0/1]\) 表示在以 \(i\) 为根节点的子树中除节点 \(i\) 的全部节点被覆盖而且使用了 \(j\) 个监听设备时节点 \(i\) 的状况，第一个 \([0/1]\) 表示有没有放置监听设备，第二个 \([0/1]\) 表示 \(i\) 有没有被覆盖。

有：

\(f[u][i + j][0][0] = \sum f[u][i][0][0] \times f[v][j][0][1]\)

\(f[u][i + j][0][1] = \sum f[u][i][0][1] \times (f[v][j][0][1] + f[v][j][1][1]) + f[u][i][0][0] \times f[v][j][1][1]\)

\(f[u][i + j][1][0] = \sum f[u][i][1][0] \times (f[v][j][0][0] + f[v][j][0][1])\)

\(f[u][i + j][1][1] = \sum f[u][i][1][1] \times (f[v][j][0][0] + f[v][j][0][1] + f[v][j][1][0] + f[v][j][1][1]) + f[u][i][1][0] \times (f[v][j][1][0] + f[v][j][1][1])\)

注意：

1. 每次计算时都要把 \(f[u]\) 清空重新统计，所以只能用 \(tmp\) 数组当一下“替身 ”了。*

2. 此题卡空间、时间。

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <vector>
  7. using namespace std;
  9. const int N = 100010, M = 110, mod = 1000000007;
  11. struct Edge {
  12. 	int to, next;
  13. }e[N * 2];
  15. int head[N], idx;
  17. void add(int a, int b) {
  18. 	idx++;
  19. 	e[idx].to = b;
  20. 	e[idx].next = head[a];
  21. 	head[a] = idx;
  22. }
  24. struct num {
  25. 	int x;
  26. 	num operator+(num b) {
  27. 		while (b.x >= mod) b.x -= mod;
  28. 		long long tmp = 1ll * x + b.x;
  29. 		while (tmp >= mod) tmp -= mod;
  30. 		num res;
  31. 		res.x = tmp;
  32. 		return res;
  33. 	}
  35. 	void operator+=(num b) {
  36. 		while (b.x >= mod) b.x -= mod;
  37. 		long long tmp = 1ll * x + b.x;
  38. 		while (tmp >= mod) tmp -= mod;
  39. 		x = tmp;
  40. 	}
  42. 	num operator*(num b) {
  43. 		num res;
  44. 		res.x = (1ll * x * b.x) % mod;
  45. 		return res;
  46. 	}
  48. 	void operator=(int k) {
  49. 		x = k;
  50. 	}
  51. };
  53. int n, k;
  54. int sz[N];
  55. num f[N][M][2][2];
  56. num t[M][2][2];
  58. void dfs(int u, int fa) {
  59. 	sz[u] = 1;
  60. 	f[u][0][0][0] = 1;
  61. 	f[u][1][1][0] = 1;
  62. 	for (int tmp = head[u]; tmp; tmp = e[tmp].next) {
  63. 		int v = e[tmp].to;
  64. 		if (v == fa) continue;
  65. 		dfs(v, u);
  66. 		memcpy(t, f[u], sizeof(t));
  67. 		memset(f[u], 0, sizeof(f[u]));
  68. 		for (int i = min(sz[u], k); i >= 0; i--) {
  69. 			for (int j = 0; j <= min(sz[v], k - i); j++) {
  70. 				f[u][i + j][0][0] += t[i][0][0] * f[v][j][0][1];
  71. 				f[u][i + j][0][1] += t[i][0][1] * (f[v][j][0][1] + f[v][j][1][1]) + t[i][0][0] * f[v][j][1][1];
  72. 				f[u][i + j][1][0] += t[i][1][0] * (f[v][j][0][0] + f[v][j][0][1]);
  73. 				f[u][i + j][1][1] += t[i][1][1] * (f[v][j][0][0] + f[v][j][0][1] + f[v][j][1][0] + f[v][j][1][1]) + t[i][1][0] * (f[v][j][1][0] + f[v][j][1][1]);
  74. 			}
  75. 		}
  76. 		sz[u] += sz[v];
  77. 	}
  78. }
  80. int main() {
  81. 	ios::sync_with_stdio(false);
  82. 	cin.tie(nullptr);
  84. 	cin >> n >> k;
  85. 	for (int i = 1; i < n; i++) {
  86. 		int x, y;
  87. 		cin >> x >> y;
  88. 		add(x, y);
  89. 		add(y, x);
  90. 	}
  91. 	dfs(1, 0);
  92. 	cout << (f[1][k][0][1] + f[1][k][1][1]).x << '\n';
  93. 	return 0;
  94. }

换根DP

换根法思路：

  1. 自下而上递推；
  2. 自上而下递推。

P3478 [POI2008] STA-Station

题目描述：

image

思路：

个节点 \(u\) 为根的子树大小 \(s[u]\)。

然后我们设 \(f[i]\) 为以 \(i\) 为根时所有节点的深度之和，\(j\) 为 \(i\) 的子节点。

那么对于所有 \(j\) 的子节点，深度都减 \(1\)，所以总共减少了 \(s[j]\)。

对于所有不是 \(j\) 的子节点的节点，深度都加 \(1\) ，所以总共加了 \(n - s[j]\)。

所以 \(f[j] = f[i] - s[j] + n - s[j] = f[i] + n - 2 \times s[j]\)。

最后取 \(\max\) 即可。

代码：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  6. using i64 = long long;
  8. const int N = 1000010;
  10. struct Edge {
  11. 	int to, next;
  12. }e[N * 2];
  14. int head[N], idx;
  16. void add(int a, int b) {
  17. 	idx++;
  18. 	e[idx].to = b;
  19. 	e[idx].next = head[a];
  20. 	head[a] = idx;
  21. }
  23. int n;
  24. int sz[N];
  26. void dfs1(int u, int fa) {
  27. 	sz[u] = 1;
  28. 	for (int i = head[u]; i; i = e[i].next) {
  29. 		int to = e[i].to;
  30. 		if (to == fa) continue;
  31. 		dfs1(to, u);
  32. 		sz[u] += sz[to];
  33. 	}
  34. }
  36. int f[N];
  37. int maxv, ans;
  39. void dfs2(int u, int fa) {
  40. 	for (int i = head[u]; i; i = e[i].next) {
  41. 		int to = e[i].to;
  42. 		if (to == fa) continue;
  43. 		f[to] = f[u] + n - 2 * sz[to];
  44. 		dfs2(to, u);
  45. 	}
  46. }
  48. int main() {
  49. 	ios::sync_with_stdio(false);
  50. 	cin.tie(nullptr);
  52. 	cin >> n;
  53. 	for (int i = 1; i < n; i++) {
  54. 		int x, y;
  55. 		cin >> x >> y;
  56. 		add(x, y);
  57. 		add(y, x);
  58. 	}
  59. 	dfs1(1, 0);
  60. 	for (int i = 1; i <= n; i++) f[1] += sz[i];
  61. 	dfs2(1, 0);
  62. 	for (int i = 1; i <= n; i++) if (f[i] > maxv) maxv = f[i], ans = i;
  63. 	cout << ans << '\n';
  64. 	return 0;
  65. }

AcWing 287. 积蓄程度 / POJ 3585 Accumulation Degree

题目描述：

image

思路：

设 \(d[i]\) 表示 \(i\) 点可以向下传递的最大流量。

设 \(f[i]\) 表示 \(i\) 点可以向外传递的最大流量（包括向下流的流量和向上流的流量）。

先 \(\text{dfs}\) 一遍求出 \(d\)。

有：

如无特殊说明 \(to\) 表示 \(i\) 的子节点，\(edge(i, to)\) 表示 \(i\) 和 \(to\) 这条边的最大流量。

\(d[i] = \sum \min(d[to], edge(i, to))\)

\(f[to] = \min(edge(i, to), f[i] - \min(edge(i, to), d[to]))\)

同时注意如果根的度为 \(1\)（如下图） ，那么计算它的子节点时要采用公式：

\(f[i] = f[to] + edge(i, to)\)

image

代码：

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 200010, INF = 0x3f3f3f3f;
  9. struct Edge {
  10. 	int to;
  11. 	int next;
  12. 	int w;
  13. }e[N * 2];
  15. int head[N], idx, deg[N];
  17. void add(int a, int b, int c) {
  18. 	idx++;
  19. 	e[idx].to = b;
  20. 	e[idx].next = head[a];
  21. 	e[idx].w = c;
  22. 	head[a] = idx;
  23. }
  25. int n;
  26. int f[N], d[N];
  28. int dfs1(int u, int fa) {
  29. 	for (int i = head[u]; i; i = e[i].next) {
  30. 		int to = e[i].to;
  31. 		if (to == fa) continue;
  32. 		d[u] += min(dfs1(to, u), e[i].w);
  33. 	}
  34. 	if (deg[u] == 1) return INF;
  35. 	return d[u];
  36. }
  38. void dfs2(int u, int fa) {
  39. 	for (int i = head[u]; i; i = e[i].next) {
  40. 		int to = e[i].to;
  41. 		if (to == fa) continue;
  42. 		if (deg[u] == 1) f[to] = d[to] + e[i].w;
  43. 		else f[to] = d[to] + min(e[i].w, f[u] - min(d[to], e[i].w));
  44. 		dfs2(to, u);
  45. 	}
  46. }
  48. void solve() {
  49. 	idx = 0;
  50. 	memset(head, 0, sizeof(head));
  51. 	memset(deg, 0, sizeof(deg));
  52. 	memset(f, 0, sizeof(f));
  53. 	memset(d, 0, sizeof(d));
  54. 	cin >> n;
  55. 	for (int i = 1; i < n; i++) {
  56. 		int x, y, z;
  57. 		cin >> x >> y >> z;
  58. 		add(x, y, z);
  59. 		add(y, x, z);
  60. 		deg[x]++;
  61. 		deg[y]++;
  62. 	}
  63. 	dfs1(1, 0);
  64. 	f[1] = d[1];
  65. 	dfs2(1, 0);
  66. 	int ans = 0;
  67. 	for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
  68. 	cout << ans << '\n';
  69. }
  71. int main() {
  72. 	ios::sync_with_stdio(false);
  73. 	cin.tie(nullptr);
  75. 	int T;
  76. 	cin >> T;
  77. 	while (T--) solve();
  79. 	return 0;
  80. }

P2986 [USACO10MAR] Great Cow Gathering G

题目描述：

image

思路：

设 \(f[u]\) 表示如果选择集会的地点为 \(u\) 点时所需时间。

根据经验，我们可以得到

\(f[to] = f[u] - to\text{节点下所有奶牛个数} \times w(u, to) + (奶牛总数 - to\text{节点下所有奶牛个数}) \times w(u, to)\)。

代码：

  1. #include <bits/stdc++.h>
  3. #define int long long
  5. using namespace std;
  7. const int N = 100010, M = 200010;
  9. struct Edge {
  10.     int to;
  11.     int next;
  12.     int w;
  13. }e[M];
  15. int head[N], idx;
  17. void add(int a, int b, int c) {
  18.     idx++;
  19.     e[idx].to = b;
  20.     e[idx].next = head[a];
  21.     e[idx].w = c;
  22.     head[a] = idx;
  23. }
  25. int sz[N];
  26. int cnt[N];
  28. int dfs(int u, int fa) {
  29.     int all = 0;
  30.     sz[u] = cnt[u];
  31.     for (int i = head[u]; i; i = e[i].next) {
  32.         int to = e[i].to;
  33.         if (to == fa) continue;
  34.         all += dfs(to, u);
  35.         sz[u] += sz[to];
  36.         all += sz[to] * e[i].w;
  37.     }
  38.     return all;
  39. }
  41. int f[N], n, get_n;
  43. void dfs2(int u, int fa) {
  44.     for (int i = head[u]; i; i = e[i].next) {
  45.         int to = e[i].to;
  46.         if (to == fa) continue;
  47.         f[to] = f[u] - sz[to] * e[i].w + (get_n - sz[to]) * e[i].w;
  48.         dfs2(to, u);
  49.     }
  50. }
  52. signed main() {
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  56.     cin >> n;
  57.     for (int i = 1; i <= n; i++) cin >> cnt[i], get_n += cnt[i];
  58.     for (int i = 1; i < n; i++) {
  59.         int x, y, z;
  60.         cin >> x >> y >> z;
  61.         add(x, y, z);
  62.         add(y, x, z);
  63.     }
  65.     f[1] = dfs(1, 0);
  66.     dfs2(1, 0);
  68.     int min_sum = 0x3f3f3f3f3f3f3f3f;
  69.     for (int i = 1; i <= n; i++) {
  70.         if (min_sum > f[i]) {
  71.             min_sum = f[i];
  72.             // ans = i;
  73.         }
  74.     }
  75.     cout << min_sum << '\n';
  76.     return 0;
  77. }

P3047 [USACO12FEB]Nearby Cows G

题目描述

image

思路

使用换根DP，

设 \(dp[i][j]\) 表示以 \(i\) 为根节点的子树中深度小于等于 \(j\) 的点的权值之和。

设 \(f[i][j]\) 表示将第 \(i\) 个点作为整棵树的根节点深度小于等于 \(j\) 的点的权值之和。

image

有：

\[\begin{cases} dp[u][k] = \sum dp[to][k - 1] \f[to][j] = dp[to][j] - dp[to][j - 2] + f[u][j - 1] \end{cases} \]

\(f[to][j] = dp[to][j] - dp[to][j - 2] + f[u][j - 1]\) 表示：

image

代码：

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. const int N = 100010, M = 30;
  7. int w[N];
  9. struct Edge {
  10. 	int to;
  11. 	int next;
  12. }e[N * 2];
  14. int head[N], idx;
  16. void add(int a, int b) {
  17. 	idx++;
  18. 	e[idx].to = b;
  19. 	e[idx].next = head[a];
  20. 	head[a] = idx;
  21. }
  23. int n, k;
  24. int dp[N][M];
  25. int f[N][M];
  27. void dfs(int u, int fa) {
  28.     for (int i = 0; i <= k; i++) dp[u][i] = w[u];
  29.     for (int i = head[u]; i; i = e[i].next) {
  30.         int to = e[i].to;
  31.         if (to == fa) continue;
  32.         dfs(to, u);
  33.         for (int i = 1; i <= k; i++) dp[u][i] += dp[to][i - 1];
  34.     }
  35. }
  37. void dfs2(int u, int fa) {
  38.     for (int i = head[u]; i; i = e[i].next) {
  39.         int to = e[i].to;
  40.         if (to == fa) continue;
  41.         f[to][1] = dp[to][1] + w[u];
  42.         for (int j = k; j >= 2; j--) f[to][j] = f[u][j - 1] - dp[to][j - 2] + dp[to][j];
  43.         dfs2(to, u);
  44.     }
  45. }
  47. int main() {
  48. 	ios::sync_with_stdio(false);
  49. 	cin.tie(nullptr);
  50. 	
  51.     cin >> n >> k;
  52.     for (int i = 1; i < n; i++) {
  53.         int a, b;
  54.         cin >> a >> b;
  55.         add(a, b);
  56.         add(b, a);
  57.     }
  58.     for (int i = 1; i <= n; i++) cin >> w[i];
  59.     dfs(1, 0);
  60.     memcpy(f[1], dp[1], sizeof(f[1]));
  61.     dfs2(1, 0);
  62.     for (int i = 1; i <= n; i++) cout << f[i][k] << '\n';
  63. 	return 0;
  64. }

原文链接：https://www.cnblogs.com/PlayWithCPP/p/17586872.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C++热门文章

  • C/C++编程笔记：编写不会在C ++中编译的C程序，我教你呀！
  • 洛谷 P2085 最小函数值
  • 使用C++界面框架ImGUI开发一个简单程序
  • C++ Json解析CJsonObject的详细使用
  • C++编译错误杂记
  • 二分法（二）：采用二分法解决“最小化最大值问题”
  • C++实现json字符串与map的转换
  • C++借助curses库实现俄罗斯方块
  • 长乐培训Day5
  • 【OpenFOAM】——OpenFOAM入门算例学习

    • C++推荐文章

  • #8. 「模板」树链剖分
  • 预设型 DP
  • Standard Template Libary or C++ Standard Library
  • 一种优秀的虚拟机内存架构 - AQ
  • 如何让 MGR 不从 Primary 节点克隆数据？
  • TLScanary：Pwn中的利器
  • c++临时对象导致的生命周期问题
  • C++(Qt)-GIS开发-简易瓦片地图下载器
  • 逆向通达信 x 逆向微信 x 逆向Qt
  • C++面向对象

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号