acwing-389. 直径

发表于 分类于 阅读次数： Waline： 本文字数： 684 阅读时长 ≈ 2 分钟

考点

  • 树的直径
  • 前缀和
  • 双指针

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 50;
int n, tot = 1, head[maxn], ver[maxn], edge[maxn], nxt[maxn];
int m, a[maxn], id[maxn];
ll d[maxn], sum[maxn];
bool v[maxn];

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

int bfs(int st) {
  queue<int> q;
  memset(d, -1, sizeof(d)), memset(id, -1, sizeof(id));
  d[st] = 0, q.push(st);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = ver[i];
      if (~d[y]) continue;
      d[y] = d[x] + 1;
      q.push(y);
      id[y] = i;
    }
  }
  int ed = st;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > d[ed]) ed = i;
  }
  return ed;
}

void route(int p, int q) {
  while (q != p) {
    a[++m] = q;
    sum[m + 1] = sum[m] + edge[id[q]];
    q = ver[id[q] ^ 1];
  }
  a[++m] = p;
}

void dfs(int x) {
  v[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (v[y]) continue;
    dfs(y);
    d[x] = max(d[x], d[y] + edge[i]);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n;
  for (int x, y, z, i = 1; i < n; ++i) {
    cin >> x >> y >> z;
    add(x, y, z), add(y, x, z);
  }
  int p = bfs(1), q = bfs(p);
  route(p, q);
  memset(d, 0, sizeof(d));
  // 直径部分标记为“已访问”
  for (int i = 1; i <= m; ++i) v[a[i]] = 1;
  // 直径上的每个点，不经过直径，能走到的最远距离
  for (int i = 1; i <= m; ++i) dfs(a[i]);
  int u = -1, ucnt, v = -1, vcnt;
  // 正序一个方向
  for (int cnt = 1, i = 2; i <= m - 1; ++i, ++cnt) {
    if (d[a[i]] == sum[i]) {
      u = i, ucnt = cnt;
    }
  }
  // 逆序一个方向
  for (int cnt = 1, i = m - 1; i >= 2; --i, ++cnt) {
    if (d[a[i]] == sum[m] - sum[i]) {
      v = i, vcnt = cnt;
    }
  }
  int ans = m - 1;
  if (~u) ans -= ucnt;
  if (~v) ans -= vcnt;
  cout << sum[m] << endl;
  cout << ans << endl;
  return 0;
}

思路

直径的必须边的模拟题，上图。

假设本图有三条直径，

1 - A - C - D - B - 2、

3 - A - C - D - B - 4、

5 - C - D - 6

共三条，可以找到必须边就是CD这条边。

根据直径的性质，任意两个同一侧的直径端点到相同直径分叉点的距离均相等，

可以得知：

以A作为分叉点，那么1A等于3A；同样的，以B作为分叉点，那么2B等于4B。

以C作为分叉点，那么1C、3C等于5C；同样的，以D作为分叉点，那么2D、4D等于6D。

具体的解决方案如下：

  1. 求出任意一条直径
  2. 把直径上的所有点标记为已访问
  3. 求出直径上的所有点，不经过直径能走到的最远距离
  4. 游标u从直径起点p出发，停在最后一个满足最远距离等于路径u - ... - p长度
  5. 游标v从直径终点q出发，停在最后一个满足最远距离等于路径v - ... - q长度
  6. 此时的u - ... - v路径就是必须边