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

树的直径与最近公共祖先

树的直径

给定一棵树, 树中每条边都有一个权值, 树中两点之间的距离定义为连接两点的路径上的边权之和。树中最远的两个节点之间的距离被称为树的直径, 连接这两点的路径被称为树的最长链。后者通常也可称为直径, 即直径既是一个数值概念, 也可代指一条 路径。

树的直径一般有两种求法, 时间复杂度都是 O(N)O(N) 。我们假设树以 NN 个点 N−1N-1 条边的无向图的形式给出, 并存储在邻接表中。

树形 DP 求树的直径

不妨设 1 号节点为根, “ NN 个点 N−1N-1 条边的无向图” 就可以看作 “有根树” 。

设 D[x]D[x] 表示从节点 xx 出发走向以 xx 为根的子树, 能够到达的最远节点的距离。设 xx 的子节点为 y1,y2,⋯ ,yty_{1}, y_{2}, \cdots, y_{t} , edge(x,y)edge(x, y) 表示边权, 显然有:

D[x]=max⁡1≤i≤t{D[yi]+edge⁡(x,yi)}D[x]=\max _{1 \leq i \leq t}\left\{D\left[y_{i}\right]+\operatorname{edge}\left(x, y_{i}\right)\right\}

接下来, 我们可以考虑对每个节点 xx 求出 “经过节点 xx 的最长链的长度” F[x]F[x], 整棵树的直径就是 max⁡1≤x≤n{F[x]}\max _{1 \leq x \leq n}\{F[x]\} 。

那么如何求出 F[x]F[x] 呢? 对于 xx 的任意两个节点 yiy_{i} 和 yjy_{j}, “经过节点 xx 的最长链的长度” 可以通过四个部分构成: 从 yiy_{i} 到 yiy_{i} 子树中的最远距离, 边 (x,yi)\left(x, y_{i}\right), 边 (x,yj)\left(x, y_{j}\right), 从 yjy_{j} 到 yjy_{j} 子树中的最远距离。不妨设 j<ij<i, 因此:

F[x]=max⁡1≤j<i≤t{D[yi]+D[yj]+edge⁡(x,yi)+edge⁡(x,yj)}F[x]=\max _{1 \leq j<i \leq t}\left\{D\left[y_{i}\right]+D\left[y_{j}\right]+\operatorname{edge}\left(x, y_{i}\right)+\operatorname{edge}\left(x, y_{j}\right)\right\}

我们没有必要使用两层循环来枚举 i,ji, j 。请读者思考计算 D[x]D[x] 的过程。在子节点的循环将要枚举到 ii 时, D[x]D[x] 恰好就保存了从节点 xx 出发走向 “以 yj(j<i)y_{j}(j<i) 为根的子树”, 能够到达的最远节点的距离, 这个距离就是 max⁡1≤j<i{D[yj]+edge⁡(x,yj)}\max _{1 \leq j<i}\left\{D\left[y_{j}\right]+\operatorname{edge}\left(x, y_{j}\right)\right\} 。 所以, 此时我们先用 D[x]+D[yi]+edge⁡(x,yi)D[x]+D\left[y_{i}\right]+\operatorname{edge}\left(x, y_{i}\right) 更新 F[x]F[x], 再用 D[yi]+edge⁡(x,yi)D\left[y_{i}\right]+\operatorname{edge}\left(x, y_{i}\right) 更新 D[x]D[x] 即可。

1
2
3
4
5
6
7
8
9
10
11
// 树形DP求树的直径
void dp(int x) {
    v[x] = 1;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (v[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
}

两次 BFS 求树的直径

通过两次 BFS 或者两次 DFS 也可以求出树的直径, 并且更容易计算出直径上的具体节点。详细地说, 这种做法包括两步:

  1. 从任意一个节点出发, 通过 BFS 或 DFS 对树进行一次遍历, 求出与出发点距离最远的节点, 记为 pp 。
  2. 从节点 pp 出发, 通过 BFS 或 DFS 再进行一次遍历, 求出与 pp 距离最远的节点, 记为 qq 。

从 pp 到 qq 的路径就是树的一条直径。这是因为 pp 一定是直径的一端, 否则总能找到一条更长的链, 与直径的定义矛盾。请读者尝试详细证明这个结论, 此处就不再赘述。既然 pp 是直径的一端, 那么与 pp 距离最远的 qq 当然就是直径的另一端了。在第 2 步的遍历过程中, 可以记录下来每个点第一次被访问时的前驱节点。最后从 qq 递归回到 pp, 即可得到直径的具体方案。

树的直径可以作为很多树上问题的突破口。接下来我们给出两道例题。除此之外, 读者还将在图论总结与练习中解决树的直径的必须边等问题。

350. 巡逻

在一个地区有 nn 个村庄，编号为 1,2,…,n1,2,…,n。

有 n−1n-1 条道路连接着这些村庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其他任一个村庄。

每条道路的长度均为 11 个单位。

为保证该地区的安全，巡警车每天都要到所有的道路上巡逻。

警察局设在编号为 11 的村庄里，每天巡警车总是从警局出发，最终又回到警局。

为了减少总的巡逻距离，该地区准备在这些村庄之间建立 KK 条新的道路，每条新道路可以连接任意两个村庄。

两条新道路可以在同一个村庄会合或结束，甚至新道路可以是一个环。

因为资金有限，所以 KK 只能为 11 或 22。

同时，为了不浪费资金，每天巡警车必须经过新建的道路正好一次。

编写一个程序，在给定村庄间道路信息和需要新建的道路数的情况下，计算出最佳的新建道路的方案，使得总的巡逻距离最小。

输入格式

第一行包含两个整数 nn 和 KK。

接下来 n−1n-1 行每行两个整数 aa 和 bb，表示村庄 aa 和 bb 之间有一条道路。

输出格式

输出一个整数，表示新建了 KK 条道路后能达到的最小巡逻距离。

数据范围

3≤n≤1000003 \le n \le 100000,
1≤K≤21 \le K \le 2,
1≤a,b≤n1 \le a,b \le n

输入样例：

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

输出样例：

1
11

算法分析

Solution

351. 树网的核

设 T=(V,E,W)T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称 TT 为树网（treenetwork），其中 V,EV, E 分别表示结点与边的集合，WW 表示各边长度的集合，并设 TT 有 nn 个结点。

路径：树网中任何两结点 a,ba,b 都存在唯一的一条简单路径，用 d(a,b)d(a,b) 表示以 a,ba,b 为端点的路径的长度，它是该路径上各边长度之和。

我们称 d(a,b)d(a,b) 为 a,ba,b 两结点间的距离。

一点 vv 到一条路径 PP 的距离为该点与 PP 上的最近的结点的距离：

d(v，P)=min{d(v，u)}d(v，P)=min\{d(v，u)\}，uu 为路径 PP 上的结点。

树网的直径：树网中最长的路径称为树网的直径。

对于给定的树网 TT，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 ECC(F)ECC(F)：树网 TT 中距路径 FF 最远的结点到路径 FF 的距离，即：

ECC(F)=max{d(v,F),v∈V}ECC(F)=max\{d(v,F),v∈V\}

任务：对于给定的树网 T=(V,E,W)T=(V, E,W) 和非负整数 ss，求一个路径 FF，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 ss（可以等于 ss），使偏心距 ECC(F)ECC(F) 最小。

我们称这个路径为树网 T=(V,E,W)T=(V,E,W) 的核（Core）。

必要时，FF 可以退化为某个结点。

一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

输入格式

包含 nn 行： 第 11 行，两个正整数 nn 和 ss，中间用一个空格隔开，其中 nn 为树网结点的个数，ss 为树网的核的长度的上界，设结点编号依次为 1,2,…,n1, 2, …, n。

从第 22 行到第 nn 行，每行给出 33 个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。

例如，2 4 7 表示连接结点 22 与 44 的边的长度为 77。

所给的数据都是正确的，不必检验。

输出格式

只有一个非负整数，为指定意义下的最小偏心距。

数据范围

n≤500000,s<231n \le 500000,s < 2^{31}

输入样例：

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

输出样例：

1
5

算法分析

Solution

最近公共祖先（LCA）

给定一棵有根树, 若节点 zz 既是节点 xx 的祖先, 也是节点 yy 的祖先, 则称 zz 是 x,yx, y 的公共祖先。在 x,yx, y 的所有公共祖先中, 深度最大的一个称为 x,yx, y 的最近公共祖先, 记为 LCA (x,y)(x, y) 。

LCA⁡(x,y)\operatorname{LCA}(x, y) 是 xx 到根的路径与 yy 到根的路径的交会点。它也是 xx 与 yy 之间的路径上深度最小的节点。求最近公共祖先的方法通常有三种:

向上标记法

从 xx 向上走到根节点, 并标记所有经过的节点。
从 yy 向上走到根节点, 当第一次遇到己标记的节点时, 就找到了 LCA⁡(x,y)\operatorname{LCA}(x, y) 。
对于每个询问, 向上标记法的时间复杂度最坏为 O(n)O(n) 。

树上倍增法

树上倍增法是一个很重要的算法。除了求 LCA 之外, 它在很多问题中都有广泛应用。设 F[x,k]F[x, k] 表示 xx 的 2k2^{k} 辈祖先, 即从 xx 向根节点走 2k2^{k} 步到达的节点。特别地, 若该节点不存在, 则令 F[x,k]=0F[x, k]=0 。F[x,0]F[x, 0] 就是 xx 的父节点。除此之外, ∀k∈[1,log⁡n]\forall k \in [1, \log n] , F[x,k]=F[F[x,k−1],k−1]F[x, k]=F[F[x, k-1], k-1] 。

这类似于一个动态规划的过程, “阶段” 就是节点的深度。因此, 我们可以对树进行广度优先遍历, 按照层次顺序, 在节点入队之前, 计算它在 FF 数组中相应的值。

以上部分是预处理, 时间复杂度为 O(nlog⁡n)O(n \log n), 之后可以多次对不同的 x,yx, y 计算 LCA, 每次询问的时间复杂度为 O(log⁡n)O(\log n) 。

基于 FF 数组计算 LCA⁡(x,y)\operatorname{LCA}(x, y) 分为以下几步:

  1. 设 d[x]d[x] 表示 xx 的深度。不妨设 d[x]≥d[y]d[x] \geq d[y] (否则可交换 x,yx, y )。
  2. 用二进制拆分思想, 把 xx 向上调整到与 yy 同一深度。
    具体来说, 就是依次尝试从 xx 向上走 k=2log⁡n,⋯ ,21,20k=2^{\log n}, \cdots, 2^{1}, 2^{0} 步, 检查到达的节点是否比 yy 深。在每次检查中, 若是, 则令 x=F[x,k]x=F[x, k] 。
  3. 若此时 x=yx=y, 说明已经找到了 LCA, LCA 就等于 yy 。这就是上面的图中的第三种情况。
  4. 用二进制拆分思想, 把 x,yx, y 同时向上调整, 并保持深度一致且二者不相会。 具体来说, 就是依次尝试把 x,yx, y 同时向上走 k=2log⁡n,⋯ ,21,20k=2^{\log n}, \cdots, 2^{1}, 2^{0} 步, 在每次尝试 中, 若 F[x,k]≠F[y,k]F[x, k] \neq F[y, k] (即仍末相会), 则令 x=F[x,k],y=F[y,k]x=F[x, k], y=F[y, k] 。
  5. 此时 x,yx, y 必定只差一步就相会了, 它们的父节点 F[x,0]F[x, 0] 就是 LCA。

请读者画图理解, 并参阅下面的程序。程序以模板题 HDOJ2586 “How far away?” 为例, 多次查询树上两点之间的距离, 时间复杂度为 O((n+m)log⁡n)\mathrm{O}((n+m) \log 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 树上倍增法求LCA (模板题：HDOJ2586)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
const int SIZE = 50010;
int f[SIZE][20], d[SIZE], dist[SIZE];
int ver[2 * SIZE], Next[2 * SIZE], edge[2 * SIZE], head[SIZE];
int T, n, m, tot, t;
queue<int> q;

void add(int x, int y, int z) {
	ver[++tot] = y; edge[tot] = z; Next[tot] = head[x]; head[x] = tot;
}

// 预处理
void bfs() {
	q.push(1); d[1] = 1;
	while (q.size()) {
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = Next[i]) {
			int y = ver[i];
			if (d[y]) continue;
			d[y] = d[x] + 1;
			dist[y] = dist[x] + edge[i];
			f[y][0] = x;
			for (int j = 1; j <= t; j++)
				f[y][j] = f[f[y][j - 1]][j - 1];
			q.push(y);
		}
	}
}

// 回答一个询问
int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = t; i >= 0; i--)
		if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = t; i >= 0; i--)
		if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n >> m;
		t = (int)(log(n) / log(2)) + 1;
		// 清空
		for (int i = 1; i <= n; i++) head[i] = d[i] = 0;
		tot = 0;
		// 读入一棵树
		for (int i = 1; i < n; i++) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			add(x, y, z), add(y, x, z);
		}
		bfs();
		// 回答问题
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
		}
	}
}

LCA 的 Tarjan 算法

Tarjan 算法本质上是使用并查集对 “向上标记法” 的优化。它是一个离线算法, 需要把 mm 个询问一次性读入, 统一计算, 最后统一输出。时间复杂度为 O(n+m)\mathrm{O}(n+m) 。

在深度优先遍历的任意时刻, 树中节点分为三类:

  1. 已经访问完毕并且回溯的节点。在这些节点上标记一个整数 2。
  2. 已经开始递归, 但尚未回溯的节点。这些节点就是当前正在访问的节点 xx 以及 xx 的祖先。在这些节点上标记一个整数 1 。
  3. 尚未访问的节点。这些节点没有标记。

对于正在访问的节点 xx, 它到根节点的路径已经标记为 1 。若 yy 是已经访问完毕并且回溯的节点, 则 LCA⁡(x,y)\operatorname{LCA}(x, y) 就是从 yy 向上走到根, 第一个遇到的标记为 1 的节点。

可以利用并查集进行优化, 当一个节点获得整数 2 的标记时, 把它所在的集合合并到它的父节点所在的集合中（合并时它的父节点标记一定为 1, 且单独构成一个集合）。

这相当于每个完成回溯的节点都有一个指针指向它的父节点, 只需查询 yy 所在集合的代表元素 (并查集的 get 操作), 就等价于从 yy 向上一直走到一个开始递归但尚未回溯的节点 (具有标记 1), 即 LCA⁡(x,y)\operatorname{LCA}(x, y) 。

在 xx 回溯之前, 标记情况与合并情况如下图所示。黑色表示标记为 1 , 灰色表示标记为 2 , 白色表示没有标记, 箭头表示执行了合并操作。

此时扫描与 xx 相关的所有询问, 若询问当中的另一个点 yy 的标记为 2 , 就知道了该询问的回答应该是 yy 在并查集中的代表元素 (并查集中 get(y)函数的结果)。

下面的参考程序以模板题 HDOJ2586 “How far away?” 为例, 多次查询树上两点之间的距离, 时间复杂度为 O(n+m)O(n+m) 。

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
// Tarjan算法离线求LCA (模板题：HDOJ2586)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZE = 50010;
int ver[2 * SIZE], Next[2 * SIZE], edge[2 * SIZE], head[SIZE];
int fa[SIZE], d[SIZE], v[SIZE], lca[SIZE], ans[SIZE];
vector<int> query[SIZE], query_id[SIZE];
int T, n, m, tot, t;

void add(int x, int y, int z) {
	ver[++tot] = y; edge[tot] = z; Next[tot] = head[x]; head[x] = tot;
}

void add_query(int x, int y, int id) {
	query[x].push_back(y), query_id[x].push_back(id);
	query[y].push_back(x), query_id[y].push_back(id);
}

int get(int x) {
	if (x == fa[x]) return x;
	return fa[x] = get(fa[x]);
}

void tarjan(int x) {
	v[x] = 1;
	for (int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if (v[y]) continue;
		d[y] = d[x] + edge[i];
		tarjan(y);
		fa[y] = x;
	}
	for (int i = 0; i < query[x].size(); i++) {
		int y = query[x][i];
		int id = query_id[x][i];
		if (v[y] == 2) {
			int lca = get(y);
			ans[id] = min(ans[id], d[x] + d[y] - 2 * d[lca]);
		}
	}
	v[x] = 2;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			head[i] = 0;
			query[i].clear(), query_id[i].clear();
			fa[i] = i, v[i] = 0;
		}
		tot = 0;
		for (int i = 1; i < n; i++) {
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			add(x, y, z), add(y, x, z);
		}
		for (int i = 1; i <= m; i++) {
			int x, y;
			scanf("%d%d", &x, &y);
			if (x == y) ans[i] = 0;
			else {
				add_query(x, y, i);
				ans[i] = 1 << 30;
			}
		}
		tarjan(1);
		for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
	}
}

树上差分

在 “前缀和与差分” 中, 我们定义了一个序列的前缀和与差分序列, 并通过差分技巧, 把 “区间” 的增减转化为 “左端点加 1 , 右端点减 1 ”。根据 “差分序列的前缀和是原序列” 这一原理, 在树上可以进行类似的简化, 其中 “区间操作” 对应为 “路径操作”, “前缀和” 对应为 “子树和”。我们通过具体的例子来详细探讨。

352. 闇の連鎖

传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。

经过研究，你发现 Dark 呈现无向图的结构，图中有 NN 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。

Dark 有 N–1N – 1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外，Dark 还有 MM 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。

一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。

注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

输入格式

第一行包含两个整数 NN 和 MM。

之后 N–1N – 1 行，每行包括两个整数 AA 和 BB，表示 AA 和 BB 之间有一条主要边。

之后 MM 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

数据范围

N≤100000,M≤200000N \le 100000,M \le 200000，数据保证答案不超过231−12^{31}-1

输入样例：

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

输出样例：

1
3

算法分析

Solution

353. 雨天的尾巴

深绘里一直很讨厌雨天。

灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。

虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。

无奈的深绘里和村民们只好等待救济粮来维生。

不过救济粮的发放方式很特别。

有 nn 个点，形成一个树状结构。

有 mm 次发放操作，每次选择两个点 x,yx,y，对 xx 到 yy 的路径上（包括 x,yx,y）的每个点发放一袋 zz 类型的物品。

求完成所有发放操作后，每个点存放最多的是哪种类型的物品。

输入格式

第一行两个正整数 n,mn,m，含义如题目所示。

接下来 n−1n-1 行，每行两个数 (a,b)(a,b)，表示 (a,b)(a,b) 间有一条边。

再接下来 mm 行，每行三个数 (x,y,z)(x,y,z)，含义如题目所示。

输出格式

共 nn 行，第 ii 行一个整数，表示第 ii 座房屋里存放的最多的是哪种救济粮，如果有多种救济粮存放次数一样，输出编号最小的。

如果某座房屋里没有救济粮，则对应一行输出 00。

数据范围

1≤n,m≤1000001 \le n,m \le 100000,
1≤z≤1051 \le z \le 10^5

输入样例：

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

输出样例：

1
2
3
4
5
2
3
3
0
2

算法分析

Solution

354. 天天爱跑步

小 CC 同学认为跑步非常有趣，于是决定制作一款叫作《天天爱跑步》的游戏。

《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 nn 个节点和 n−1n-1 条边的树，任意两个节点存在一条路径互相可达。

树上节点的编号是 1∼n1 \sim n 之间的连续正整数。

现在有 mm 个玩家，第 ii 个玩家的起点为 SiS_i，终点为 TiT_i。

每天打卡任务开始时，所有玩家在第 00 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。

因为地图是一棵树，所以每个人的路径是唯一的。

小 CC 想知道游戏的活跃度，所以在每个节点上都放置了一个观察员。

在节点 jj 的观察员会选择在第 WjW_j 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 WjW_j 秒也正好到达了节点 jj。

小 CC 想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后，该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。

即对于把节点 jj 作为终点的玩家：若他在第 WjW_j 秒前到达终点，则在节点 jj 的观察员不能观察到该玩家；若他正好在第 WjW_j 秒到达终点，则在节点 jj 的观察员可以观察到这个玩家。

输入格式

第一行有两个整数 nn 和 mm。

其中 nn 代表树的结点数量，同时也是观察员的数量，mm 代表玩家的数量。

接下来 n−1n-1 行每行两个整数 UU 和 VV，表示结点 UU 到结点 VV 有一条边。

接下来一行 nn 个整数，其中第个整数为 WjW_j，表示结点出现观察员的时间。

接下来 mm 行，每行两个整数 SiS_i 和 TiT_i，表示一个玩家的起点和终点。

输出格式

一行 nn 个整数，第 ii 个整数表示结点 ii 的观察员可以观察到多少人。

数据范围

1≤n,m≤3×1051 \le n,m \le 3 \times 10^5

输入样例：

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

输出样例：

1
2 0 0 1 1 1

算法分析

Solution

LCA 的综合应用

355. 异象石

Adera 是 Microsoft 应用商店中的一款解谜游戏。

异象石是进入 Adera 中异时空的引导物，在 Adera 的异时空中有一张地图。

这张地图上有 NN 个点，有 N−1N-1 条双向边把它们连通起来。

起初地图上没有任何异象石，在接下来的 MM 个时刻中，每个时刻会发生以下三种类型的事件之一：

  1. 地图的某个点上出现了异象石（已经出现的不会再次出现）；
  2. 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
  3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。

输入格式

第一行有一个整数 NN，表示点的个数。

接下来 N−1N-1 行每行三个整数 x,y,zx,y,z，表示点 xx 和 yy 之间有一条长度为 zz 的双向边。

第 N+1N+1 行有一个正整数 MM。

接下来 MM 行每行是一个事件，事件是以下三种格式之一：

  • + x 表示点 xx 上出现了异象石
  • - x 表示点 xx 上的异象石被摧毁
  • ? 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

输出格式

对于每个 ? 事件，输出一个整数表示答案。

数据范围

1≤N,M≤1051 \le N,M \le 10^5,
1≤x,y≤N1 \le x,y \le N,
x≠yx \neq y,
1≤z≤1091 \le z \le 10^9

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?

输出样例：

1
2
3
4
5
14
17
10

算法分析

Solution

356. 次小生成树

给定一张 NN 个点 MM 条边的无向图，求无向图的严格次小生成树。

设最小生成树的边权之和为 sumsum，严格次小生成树就是指边权之和大于 sumsum 的生成树中最小的一个。

输入格式

第一行包含两个整数 NN 和 MM。

接下来 MM 行，每行包含三个整数 x，y，zx，y，z，表示点 xx 和点 yy 之前存在一条边，边的权值为 zz。

输出格式

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

数据范围

N≤105,M≤3×105N \le 10^5,M \le 3 \times 10^5

输入样例：

1
2
3
4
5
6
7
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6

输出样例：

1
11

算法分析

Solution

357. 疫情控制

HH 国有 nn 个城市，这 nn 个城市用 n−1n-1 条双向道路相互连通构成一棵树，11 号城市是首都，也是树中的根节点。

HH 国的首都爆发了一种危害性极高的传染病。

当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。

但要注意的是，首都是不能建立检查点的。

现在，在 HH 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。

军队总数为 mm 支。

一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。

一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问：最少需要多少个小时才能控制疫情？

注意：不同的军队可以同时移动。

输入格式

第一行一个整数 nn，表示城市个数。

接下来的 n−1n-1 行，每行 33 个整数，u、v、wu、v、w，每两个整数之间用一个空格隔开，表示从城市 uu 到城市 vv 有一条长为 ww 的道路，数据保证输入的是一棵树，且根节点编号为 11。

接下来一行一个整数 mm，表示军队个数。

接下来一行 mm 个整数，每两个整数之间用一个空格隔开，分别表示这 mm 个军队所驻扎的城市的编号。

输出格式

共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出 −1-1。

数据范围

2≤m≤n≤500002 \le m \le n \le 50000,
0<w<1090 < w < 10^9

输入样例：

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

输出样例：

1
3

算法分析

Solution