树的直径_解题技巧

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

性质

  • 多条直径必相交于一点或一条公共路径。

  • 任意两个同一侧的直径端点到相同直径分叉点的距离均相等。

  • 直径一定是最长边。

模板

两次BFS

边权均非负的情况才可以用，用于记录整条直径。

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
// 找到以bg为起点的直径
int bfs(int bg) {
  queue<int> q;
  memset(d, -1, sizeof(d));
  d[bg] = 0, q.push(bg);
  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;
      q.push(y);
      d[y] = d[x] + edge[i];
      id[y] = i;
    }
  }
  int ed = bg;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > d[ed]) ed = i;
  }
  return ed;
}

// 记录p为起点，q为终点的直径，从终点q逆推至p
// 每次记录第t个点到a，第t+1个点到b，所以最后要把起点p单独记录一次
void route(int p, int q) {
  while (q != p) {
    a[++t] = q;
    b[t + 1] = edge[id[q]];
    q = ver[id[q] ^ 1];
  }
  a[++t] = p;
}

树形DP

没有边权的正负限制，但只能保存直径的长度。

1
2
3
4
5
6
7
8
9
10
void dp(int x) {
  v[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (v[y]) continue;
    dp(y);
    l2 = max(l2, d[x] + d[y] + edge[i]);
    d[x] = max(d[x], d[y] + edge[i]);
  }
}

练习