「2023zimpha」树的直径练习题
题目传送门
给出一个有 $n$ 个点，$m$ 条边的森林，有 $q$ 次操作。操作有两种：
- 查询点 $x$ 所在树的直径
- 要求添加一条边，合并点 $x$ 和 $y$ 所在的两棵树，使合并后树的直径最小。（如果 $x$ 和 $y$ 在同一棵树中则不用操作）
$n,m,q \le 3\cdot 10^5$
设添加的边的两个端点为 $u,v$，两棵树直径分别为 $d_1,d_2$。
使合并后树的直径最小，也就是使经过 $u,v$ 的最长路径最短，这条路径的长度为 $dis(u,u’)+dis(v,v’)+1$，其中 $u’,v’$ 分别是合并前两棵树中的点。
考虑最小化 $dis(u,u’)$，那么就是要在找到一个 $u$，使得它到树中其他点距离的最大值最小。
这里有一个经典结论，从一个点到树中其他的最长路径，另一端点一定是这棵树直径的一个端点。所以我们选的 $u$ 一定是直径的中点（若直径为奇数则中间两个点任取一个）。因此 $\max(dis(u,u’))=\left\lceil\dfrac{d_1}{2}\right\rceil$。
所以，合并后树的最小直径就是 $\max\left(d1,d2,\left\lceil\dfrac{d_1}{2}\right\rceil+\left\lceil\dfrac{d_2}{2}\right\rceil\right)$。
用并查集合并即可。
Code
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
| int n, m, q, op, u, v;
vector<int> g[N];
int fa[N];
int Find(int i) {
if(fa[i] == i) return i;
else return fa[i] = Find(fa[i]);
}
int mx, id;
int d[N];
void dfs(int x, int f, int cnt) {
if(cnt > mx) mx = cnt, id = x;
for(int y: g[x]) {
if(y == f) continue;
dfs(y, x, cnt + 1);
}
}
int div2(int x) {
if(!x) return 0;
else return (x - 1) / 2 + 1;
}
void solve() {
cin >> n >> m >> q;
rep(i, n) fa[i] = i;
rep(i, m) {
cin >> u >> v;
u--, v--;
g[u].pb(v), g[v].pb(u);
fa[Find(u)] = Find(v);
}
memset(d, -1, sizeof(d));
rep(i, n) if(d[Find(i)] == -1) {
mx = -1;
dfs(i, -1, 0);
mx = -1;
dfs(id, -1, 0);
d[Find(i)] = mx;
}
while(q--) {
cin >> op;
if(op == 1) {
cin >> u;
u--;
cout << d[Find(u)] << '\n';
}
else {
cin >> u >> v;
u--, v--;
if(Find(u) == Find(v)) continue;
else {
d[Find(v)] = max(max(d[Find(u)], d[Find(v)]), div2(d[Find(u)]) + div2(d[Find(v)]) + 1);
fa[Find(u)] = Find(v);
}
}
}
}
|