原题链接 Luogu
题面描述
给出一棵树，求有多少条边被所有直径同时覆盖。
解题思路
首先考虑求出一条直径的方法：Link
用两遍 DFS 至少能求出一条直径。怎么知道其中的哪些边被所有直径覆盖呢？
直径有一个性质：在边权为正时，所有直径的中点（可能正好在一个点上，也可能在一条边上）重合。
感性理解一下：如果有两条直径，首先他们应该相交，否则把它们连在一起一定更优；如果它们相交的地方并不是中点，比如这样：
那么把两端直径中较长的一段分别取出，就能拼出更长的直径（图中红 2 蓝 4）。
根据上面的性质，所有直径应该在中间重合，然后在两端分叉。我们只要找到离中点最近的两个分叉点，则分叉点之间的部分都是重合的。
所以我们要从中点出发，分别向两端枚举，如果发现分叉就结束。
那应该如何判断分叉呢？
由于直径的性质，我们可以知道，对于直径上一个不是分叉点的点，它不经过直径能到达的最远点应该比直径的端点更近（否则选取这个点就又是一条直径）。反过来，如果不经过直径能到达的最远点和直径的端点一样远，就说明那个“最远点”是另一条直径的端点，则当前点就是分叉点。
AC 代码
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <bits/stdc++.h>
using namespace std;
#define FILE_IO
namespace io {...};
using namespace io;
const int maxn = 2e5 + 5;
int n;
vector<pair<int, long long> > tree[maxn];
long long dis[maxn];
int f[maxn];
void dfs(int u, int f) {
for (auto e : tree[u]) {
if (e.first == f) continue;
dis[e.first] = dis[u] + e.second;
dfs(e.first, u);
}
}
void dfs2(int u) {
for (auto e : tree[u]) {
if (e.first == f[u]) continue;
f[e.first] = u;
dis[e.first] = dis[u] + e.second;
dfs2(e.first);
}
}
bool book[maxn];
long long dfs3(int u) {
book[u] = true;
long long res = 0;
for (auto e : tree[u]) {
if (book[e.first]) continue;
res = max(res, e.second + dfs3(e.first));
}
return res;
}
int main() {
read(n);
for (int i = 1; i < n; i++) {
int u, v; long long w; read(u); read(v); read(w);
tree[u].emplace_back(v, w);
tree[v].emplace_back(u, w);
}
dis[1] = 0;
dfs(1, 0);
int l = 1;
for (int i = 2; i <= n; i++) {
if (dis[i] > dis[l]) l = i;
}
dis[l] = 0;
f[l] = l;
dfs2(l);
int r = 1;
for (int i = 2; i <= n; i++) {
if (dis[i] > dis[r]) r = i;
}
int u = r; book[r] = true;
while (u != l) {
u = f[u];
book[u] = true;
}
u = r;
int ll = l, rr = r;
while (u != l) {
u = f[u];
long long tmp = dfs3(u);
if (dis[u] >= dis[r] >> 1 && tmp == dis[r] - dis[u]) {
rr = u;
}
if (dis[u] <= dis[r] >> 1 && tmp == dis[u]) {
ll = u;
break;
}
}
u = rr;
int cnt = 0;
while (u != ll) {
cnt++;
u = f[u];
}
write(dis[r]);
write(cnt);
return 0;
}
|
