参考《算法竞赛进阶指南》、AcWing题库

image-20211124110759935

给定一棵有 NN 个节点的树 (通常是无根树, 也就是有 N−1N-1 条无向边), 我们可以任选一个节点为根节点, 从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时, 一般就以节点从深到浅 (子树从小到大) 的顺序作为 DP 的 “阶段”。 DP 的状态表示中, 第一维通常是节点编号 (代表以该节点为根的子树)。大多数时候, 我们采用递归的方式实现树形动态规划。对于每个节点 xx, 先递归在它的每个子节点上进行 DP，在回溯时，从子节点向节点 xx 进行状态转移。

285. 没有上司的舞会

题目描述

Ural 大学有 NN 名职员，编号为 1∼N1 \sim N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 HiH_i 给出，其中 1≤i≤N1 \le i \le N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 NN。

接下来 NN 行，第 ii 行表示 ii 号职员的快乐指数 HiH_i。

接下来 N−1N-1 行，每行输入一对整数 L,KL, K，表示 KK 是 LL 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤60001 \le N \le 6000,
−128≤Hi≤127-128 \le H_i \le 127

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

1
5

算法分析

最大独立集问题，每条边最多选择一个点。

我们就以节点编号 (子树的根) 作为 DP 状态的第一维。因为一名职员是否愿意参加只跟他的直接上司是否参加有关, 所以我们在每棵子树递归完成时, 保留两个 “代表信息” 一一根节点参加时整棵子树的最大快乐指数和, 以及根节点不参加时整棵子树的最大快乐指数和, 就可以满足 “最优子结构” 性质了。

设 F[x,0]F[x, 0] 表示从以 xx 为根的子树中邀请一部分职员参会, 并且 xx 不参加舞会时, 快乐指数总和的最大值。此时, xx 的子节点 (直接下属) 可以参会, 也可以不参会。

F[x,0]=∑s∈Son⁡(x)max⁡(F[s,0],F[s,1])F[x, 0]=\sum_{s \in \operatorname{Son}(x)} \max (F[s, 0], F[s, 1])

设 F[x,1]F[x, 1] 表示从以 xx 为根的子树中邀请一部分职员参会, 并且 xx 参加舞会时, 快乐指数总和的最大值。此时, xx 的所有子节点 (直接下属) 都不能参会。

F[x,1]=H[x]+∑s∈Son⁡(x)F[s,0]F[x, 1]=H[x]+\sum_{s \in \operatorname{Son}(x)} F[s, 0]

其中, Son⁡(x)\operatorname{Son}(x) 表示 xx 的子节点集合。

本题输入的是一棵有根树 (指定了节点间的上下属关系), 故我们需要先找出没有上司的节点 rootroot 作为根, DP 的目标为 max⁡(F[root,0],F[root,1])\max (F[r o o t, 0], F[r o o t, 1]) 。时间复杂度 O(N)O(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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> son[10010];
int f[10010][2], v[10010], h[10010], n;

void dp(int x) {
    f[x][0] = 0;
	f[x][1] = h[x];
	for (int i = 0; i < son[x].size(); i++) {
		int y = son[x][i];
		dp(y);
		f[x][0] += max(f[y][0], f[y][1]);
		f[x][1] += f[y][0];
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		v[x] = 1; // x has a father
		son[y].push_back(x); // x is a son of y
	}
	int root;
	for (int i = 1; i <= n; i++)
		if (!v[i]) { // i doesn't have a father
            root = i;
            break;
        }
	dp(root);
	cout << max(f[root][0], f[root][1]) << endl;
}

正如深度优先和广度优先都可以对树或图进行遍历一样, 除了自顶向下的递归外, 我们也可以用自底向上的拓扑排序来执行树形 DP。通常前者已经足够, 这里我们就不再赘述。

在更多的题目中, 树是以一张 NN 个点、 N−1N-1 条边的无向图的形式给出的。在这种情况下使用树形 DP 算法时, 我们就要用邻接表存下来这 N−1N-1 条无向边, 任选一个点出发执行深度优先遍历, 并注意标记节点是否已经被访问过, 以避免在遍历中沿着反向边回到父节点。

Solution

1072. 树的最长路径

题目描述

给定一棵树，树中包含 nn 个结点（编号11~nn）和 n−1n-1 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式

第一行包含整数 nn。

接下来 n−1n-1 行，每行包含三个整数 ai,bi,cia_i,b_i,c_i，表示点 aia_i 和 bib_i 之间存在一条权值为 cic_i 的边。

输出格式

输出一个整数，表示树的最长路径的长度。

数据范围

1≤n≤100001 \le n \le 10000,
1≤ai,bi≤n1 \le a_i,b_i \le n,
−105≤ci≤105-10^5 \le c_i \le 10^5

输入样例：

1
2
3
4
5
6
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

输出样例：

1
22

算法分析

没有边权的树，求直径：

1.任取一点作为起点，找到距离该点最远的一个点u，BFS，DFS

2.再找到距离u最远的一点v。BFS，DFS

那么u和v之间的路径就是一条直径

Solution

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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010, M = N * 2; //无向边

int n;
int h[N], e[M], w[M], ne[M], idx;
int ans;

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; 
}

//dfs返回的是从当前点往下走的最大长度
int dfs(int u, int father) {
  int d1 = 0, d2 = 0;//负数边当作不存在
  
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == father) continue;//防止往上走
    int d = dfs(j, u) + w[i];
    if (d >= d1) d2 = d1, d1 = d;
    else if (d > d2) d2 = d;
  }
  
  ans = max(ans, d1 + d2);
  
  return d1;
}


int main() {
  cin >> n;
  
  memset(h, -1, sizeof h);
  for (int i = 1; i < n; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    add(b, a, c);
  }
  
  dfs(1, -1);
  
  cout << ans;
}

1073. 树的中心

题目描述

给定一棵树，树中包含 nn 个结点（编号11~nn）和 n−1n-1 条无向边，每条边都有一个权值。

请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 nn。

接下来 n−1n-1 行，每行包含三个整数 ai,bi,cia_i,b_i,c_i，表示点 aia_i 和 bib_i 之间存在一条权值为 cic_i 的边。

输出格式

输出一个整数，表示所求点到树中其他结点的最远距离。

数据范围

1≤n≤100001 \le n \le 10000,
1≤ai,bi≤n1 \le a_i,b_i \le n,
1≤ci≤1051 \le c_i \le 10^5

输入样例：

1
2
3
4
5
5 
2 1 1 
3 2 1 
4 3 1 
5 1 1

输出样例：

1
2

算法分析

向下走：DFS求最大长度

向上走：

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], up[N];//d1,d2存的是往下走的最长、次长距离，up是向上走的最长距离
int path[N];//path存的是往下走的最长距离是经过哪个子节点

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dfs_down(int u, int father) {
  d1[u] = d2[u] = -INF;//可以处理负权边情况
  
  if (h[u] == -1) return 0;
  
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == father) continue;
    int d = w[i] + dfs_down(j, u);
    if (d >= d1[u]) {
      d2[u] = d1[u], d1[u] = d;
      path[u] = j;
    } else if (d > d2[u]) {
      d2[u] = d;
    }
  }
  if (d1[u] == -INF) d1[u] = d2[u] = 0; //没有更新过，表示是叶节点
  
  return d1[u];
}

void dfs_up(int u, int father) {
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (j == father) continue;
    //子节点利用父节点来更新信息，最开始有up[root] = 0
    if (path[u] == j) up[j] =  w[i] + max(up[u], d2[u]);
    else up[j] = w[i] + max(up[u], d1[u]);
    
    dfs_up(j, u);
  }
}

int main() {
  cin >> n;
  memset(h, -1, sizeof h);
  
  for (int i = 1; i < n; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    add(b, a, c);
  }
  
  dfs_down(1, -1);
  dfs_up(1, -1);
  
  int ans = INF;
  for (int i = 1; i <= n; ++i) ans = min(ans, max(d1[i], up[i]));
  cout << ans;
}

1075. 数字转换

题目描述

如果一个数 xx 的约数之和 yy（不包括他本身）比他本身小，那么 xx 可以变成 yy，yy 也可以变成 xx。

例如，44 可以变为 33，33可以变成 11 ， 11 可以变为 77。

限定所有数字变换在不超过 nn 的正整数范围内进行，求不断进行数字变换且不出现重复数字的最多变换步数。

输入格式

输入一个正整数 nn。

输出格式

输出不断进行数字变换且不出现重复数字的最多变换步数。

数据范围

1≤n≤500001 \le n \le 50000

输入样例：

1
7

输出样例：

1
3

样例解释

一种方案为：4→3→1→74 \to 3 \to 1 \to 7。

算法分析

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 50010;

int n;
int h[N], e[N], ne[N], idx;
int sum[N];
bool st[N];
int ans;

void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u) {
  int d1 = 0, d2 = 0;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    int d = 1 + dfs(j);
    if (d >= d1) d2 = d1, d1 = d;
    else if (d > d2) d2 = d;
  }
  ans = max(ans, d1 + d2);
  return d1;
}

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) 
    for (int j = 2; j <= n / i; ++j) sum[i * j] += i;
  
  memset(h, -1, sizeof h);
  
  for (int i = 2; i <= n; ++i) 
    if (i > sum[i]) {
      add(sum[i], i);
      st[i] = true;
    }
    
  for (int i = 1; i <= n; ++i) {
    if (st[i] == false) {
      dfs(i);
    }
  }
  
  cout << ans << endl;
  
}

1074. 二叉苹果树（背包类树形DP）

题目描述

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共 NN 个节点，编号为 11 至 NN，树根编号一定为 11。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

这里的保留是指最终与1号点连通。

输入格式

第一行包含两个整数 NN 和 QQ，分别表示树的节点数以及要保留的树枝数量。

接下来 N−1N-1 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出格式

输出仅一行，表示最多能留住的苹果的数量。

数据范围

1≤Q<N≤1001 \le Q \lt N \le 100.
N≠1N \neq 1,
每根树枝上苹果不超过 3000030000 个。

输入样例：

1
2
3
4
5
5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出样例：

1
21

算法分析

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father) {
  //分组背包问题，有依赖的背包
  for (int i = h[u]; ~i; i = ne[i]) {//物品组
    int v = e[i];
    if (v == father) continue;
    
    dfs(v, u);
    
    for (int j = m; j >= 0; --j) {//体积
      for (int k = 0; k <= j - 1; ++k) {//决策
        int vk = k + 1, wk = f[v][k] + w[i];//当前物品组第k个物品的体积和价值
        f[u][j] = max(f[u][j], f[u][j - vk] + wk);
      }
    }
  }
}

int main() {
  cin >> n >> m;
  memset(h, -1, sizeof h);
  for (int i = 1; i < n; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
    add(b, a, c);
  }
  
  dfs(1, -1);
  
  cout << f[1][m];
}

323. 战略游戏

题目描述

鲍勃喜欢玩电脑游戏，特别是战略游戏，但有时他找不到解决问题的方法，这让他很伤心。

现在他有以下问题。

他必须保护一座中世纪城市，这条城市的道路构成了一棵树。

每个节点上的士兵可以观察到所有和这个点相连的边。

他必须在节点上放置最少数量的士兵，以便他们可以观察到所有的边。

你能帮助他吗？

例如，下面的树：

1463_1.jpg.gif

只需要放置 11 名士兵（在节点 11 处），就可观察到所有的边。

输入格式

输入包含多组测试数据，每组测试数据用以描述一棵树。

对于每组测试数据，第一行包含整数 NN，表示树的节点数目。

接下来 NN 行，每行按如下方法描述一个节点。

节点编号：(子节点数目) 子节点 子节点 …

节点编号从 00 到 N−1N-1，每个节点的子节点数量均不超过 1010，每个边在输入数据中只出现一次。

输出格式

对于每组测试数据，输出一个占据一行的结果，表示最少需要的士兵数。

数据范围

0<N≤15000 < N \le 1500,
一个测试点所有 NN 相加之和不超过 300650300650。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

输出样例：

1
2
1
2

算法分析

每条边至少选择一个点

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1510;

int n;
int h[N], e[N], ne[N], idx;
int f[N][2];
bool st[N];

void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
  f[u][0] = 0;
  f[u][1] = 1;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    
    dfs(j);
    
    f[u][0] += f[j][1];
    f[u][1] += min(f[j][0], f[j][1]);
  }
}

int main() {
  while (cin >> n) {
    memset(h, -1, sizeof h);
    idx = 0;
    memset(st, false, sizeof st);
    for (int i = 0; i < n; ++i) {
      int id, cnt;
      scanf("%d:(%d)", &id, &cnt);
      while (cnt--) {
        int v;
        scanf("%d", &v);
        add(id, v);
        st[v] = true;//有父节点
      }
    }
    
    int root = 0;
    while (st[root]) ++root;//找到根节点
    
    dfs(root);
    
    cout << min(f[root][0], f[root][1]) << endl;
  }
}

1077. 皇宫看守

题目描述

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。

已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。

大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式

输入中数据描述一棵树，描述如下：

第一行 nn，表示树中结点的数目。

第二行至第 n+1n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 ii，在该宫殿安置侍卫所需的经费 kk，该结点的子结点数 mm，接下来 mm 个数，分别是这个结点的 mm 个子结点的标号 r1,r2,…,rmr_1,r_2,…,r_m。

对于一个 nn 个结点的树，结点标号在 11 到 nn 之间，且标号不重复。

输出格式

输出一个整数，表示最少的经费。

数据范围

1≤n≤15001 \le n \le 1500

输入样例：

1
2
3
4
5
6
7
6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出样例：

1
25

样例解释：

在2、3、4结点安排护卫，可以观察到全部宫殿，所需经费最少，为 16 + 5 + 4 = 25。

算法分析

Solution

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1510;

int n;
int f[N][3];
int h[N], e[N], ne[N], idx;
int w[N];
bool st[N];

void add(int a, int b) {
  e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u) {
  f[u][2] = w[u];
  
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    
    dfs(j);
    
    f[u][0] += min(f[j][1], f[j][2]);
    f[u][2] += min({f[j][0], f[j][1], f[j][2]});
  }
  
  f[u][1] = 1e9;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
  }
}


int main() {
  cin >> n;
  
  memset(h, -1, sizeof h);
  for (int i = 1; i <= n; ++i) {
    int id, cnt;
    cin >> id >> w[id] >> cnt;
    while (cnt--) {
      int son;
      cin >> son;
      add(id, son);
      st[son] = true;
    }
  }
  
  int root = 1;
  while (st[root]) ++root;
  
  dfs(root);
  
  cout << min(f[root][1], f[root][2]) << endl;
}