跳转至

树的直径⚓︎

树的直径是指树中任意两个节点之间路径长度的最大值。

树的直径有如下性质：

  1. 如果有多条直径，那么这些直径一定拥有共同的中间部分，可能是一个公共点或一段公共路径
  2. 树上任意一点，相隔最远的点的集合，直径的两端点至少有一个在其中
【模板】树的直径

适用于边权非负的树，不仅能得到直径的长度，还能得到直径沿途所有点

要求边权非负

本题中边权可能为负数，不能通过全部测试

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  int u, v, w;
  vector<vector<pair<int, int>>> tree(n + 1);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  int root     = 1;     // 起始节点, 任选一个节点作为根
  int farthest = root;  // 距离root最远的节点

  vector<int> dist(n + 1, 0);   // 节点到root的距离
  vector<int> last(n + 1, -1);  // x的前一个节点, 用于回溯直径路径

  std::function<void(int, int)> dfs = [&](int x, int from, int weight = 1) {
    for (const auto &[y, w] : tree[x]) {
      if (y != from) {
        last[y] = x;
        dist[y] = dist[x] + w;
        if (dist[y] > dist[farthest]) { farthest = y; }
        dfs(y, x);
      }
    }
  };
  // 第一次dfs，找到距离root最远的节点farthest
  dfs(root, -1);
  // 第二次dfs，以farthest为root，找到距离farthest最远的节点，距离即为直径
  fill(dist.begin(), dist.end(), 0);
  last[farthest] = -1;  // 重置farthest的前一个节点
  root           = farthest;
  farthest       = root;
  dfs(root, -1);

  cout << dist[farthest] << "\n";
  return 0;
}

适用于边权可以为负的树，只能得到直径的长度

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  int u, v, w;
  vector<vector<pair<int, int>>> tree(n + 1);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  int root     = 1;  // 起始节点, 任选一个节点作为根
  int diameter = 0;  // 直径

  vector<int> max_dist(n + 1, 0);  // 以x为根的子树中，x到某个节点的最大距离
  vector<int> answer(n + 1, 0);    // 经过x的最长路径

  std::function<void(int, int)> dfs = [&](int x, int from) {
    for (const auto &[y, w] : tree[x]) {
      if (y != from) {
        dfs(y, x);
        answer[x]   = max(answer[x], max_dist[x] + max_dist[y] + w);  // 更新经过x的最长路径
        max_dist[x] = max(max_dist[x], max_dist[y] + w);              // 更新x到某个节点的最大距离
      }
    }
    diameter = max(diameter, answer[x]);
  };
  dfs(root, -1);

  cout << diameter << "\n";

  return 0;
}

省略了 answer 数组，直接在 dfs 中更新直径

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  int u, v, w;
  vector<vector<pair<int, int>>> tree(n + 1);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  int root     = 1;  // 起始节点, 任选一个节点作为根
  int diameter = 0;  // 直径

  vector<int> max_dist(n + 1, 0);  // 以x为根的子树中，x到某个节点的最大距离

  std::function<void(int, int)> dfs = [&](int x, int from) {
    int first_max = 0, second_max = 0;  // (1)!
    for (const auto &[y, w] : tree[x]) {
      if (y != from) {
        dfs(y, x);
        if (max_dist[y] + w >= first_max) {
          second_max = first_max;
          first_max  = max_dist[y] + w;
        } else if (max_dist[y] + w > second_max) {
          second_max = max_dist[y] + w;
        }
      }
    }
    diameter    = max(diameter, first_max + second_max);
    max_dist[x] = first_max;
  };
  dfs(root, -1);

  cout << diameter << "\n";

  return 0;
}

  1. first_max 和 second_max 分别记录子节点中最大的和第二大的 max_dist，这样可以避免在更新 diameter 时重复计算。

C++
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  int u, v, w;
  vector<vector<pair<int, int>>> tree(n + 1);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  int root     = 1;  // 起始节点, 任选一个节点作为根
  int diameter = 0;  // 直径

  vector<int> max_dist(n + 1, 0);  // 以x为根的子树中，x到某个节点的最大距离

  std::function<void(int, int)> dfs = [&](int x, int from) {
    for (const auto &[y, w] : tree[x]) {
      if (y != from) {
        dfs(y, x);
        diameter    = max(diameter, max_dist[x] + max_dist[y] + w);  // (1)!
        max_dist[x] = max(max_dist[x], max_dist[y] + w);             // 更新x到某个节点的最大距离
      }
    }
  };
  dfs(root, -1);

  cout << diameter << "\n";

  return 0;
}

  1. 更新经过x的最长路径，必须在更新max_dist[x]之前，因为max_dist[x]此时记录的是已经遍历过的子节点中最大的max_dist。否则y节点的贡献会被错误计算。

直径的公共部分⚓︎

由于树的直径可能不唯一，但它们一定拥有共同的中间部分，可能是一个公共点或一段公共路径。

如果树的边权都为正数，可以通过两次 \text{DFS} 找到一条直径，然后从直径的两个端点同时向中间移动，直到相遇，所经过的路径即为所有直径的公共部分。

直径

对于给定的一棵树，边权为正整数，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

C++
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int n;
  cin >> n;
  vector<vector<pair<int64_t, int64_t>>> tree(n + 1);
  for (int i = 1; i < n; ++i) {
    int64_t u, v, w;
    cin >> u >> v >> w;
    tree[u].emplace_back(v, w);
    tree[v].emplace_back(u, w);
  }
  int64_t root     = 1;
  int64_t farthest = root;  // 距离root最远的节点

  vector<int64_t> dist(n + 1, 0);   // 节点到root的距离
  vector<int64_t> last(n + 1, -1);  // x的前一个节点

  std::function<void(int64_t, int64_t)> dfs = [&](int64_t x, int64_t from) {
    for (const auto &[y, w] : tree[x]) {
      if (y != from) {
        last[y] = x;
        dist[y] = dist[x] + w;
        if (dist[y] > dist[farthest]) { farthest = y; }
        dfs(y, x);
      }
    }
  };
  dfs(root, -1);
  fill(dist.begin(), dist.end(), 0);
  last[farthest] = -1;  // 重置farthest的前一个节点
  root           = farthest;
  farthest       = root;
  dfs(root, -1);

  int64_t diameter = dist[farthest];

  // 标记直径路径上的所有点
  vector<int64_t> is_on_diameter(n + 1);
  for (int64_t i = farthest; i != -1; i = last[i]) { is_on_diameter[i] = 1; }
  // 查找不经过直径上点的最长路径
  std::function<int64_t(int64_t, int64_t)> dfs_exclude_diameter
      = [&](int64_t x, int64_t from) -> int64_t {
    int64_t max_length = 0;
    for (const auto &[y, w] : tree[x]) {
      if (y != from && !is_on_diameter[y]) {  // 只遍历不在直径上的点
        max_length = max(max_length, dfs_exclude_diameter(y, x) + w);
      }
    }
    return max_length;
  };

  int64_t left = root, right = farthest;                      // 直径的两个端点
  for (int64_t i = last[farthest]; i != root; i = last[i]) {  // 遍历直径路径上的每个节点
    int64_t max_length = dfs_exclude_diameter(i, -1);
    // 找到公共部分的右边界, 不经过直径路径，能到达距离恰好等于直径另一端的点
    if (max_length == diameter - dist[i]) { right = i; }
    // 找到公共部分的左边界
    if (max_length == dist[i] && left == root) { left = i; }
  }

  // 收集所有的直径都经过的边
  int64_t count = 0;
  for (int64_t i = right; i != left; i = last[i]) {  // (1)!
    count++;
  }
  cout << diameter << "\n" << count << "\n";

  return 0;
}

  1. 公共边即为从 right 到 left 的路径上的边，每条边可以表示为(last[i], i)

评论