树的直径

树上任意两节点之间最长的简单路径即为树的「直径」。

显然，一棵树可以有多条直径，他们的长度相等。

可以用两次 DFS 或者树形 DP 的方法在 $O(n)$ 时间求出树的直径。

两次DFS

此做法要求树没有负边权。首先从任意节点 $y$ 开始进行第一次 DFS，到达距离其最远的节点，记为 $z$，然后再从 $z$ 开始做第二次 DFS，到达距离 $z$ 最远的节点，记为 $z'$，则 $\delta(z, z')$ 即为树的直径。

实现

#include <iostream>
#include <vector>
using namespace std;
int c = 0;  // c 为第一次dfs找到的直径的一个端点
vector<vector<pair<int, int>>> edge;
vector<int> dis, vis;

void dfs(int u) {
  vis[u] = 1;
  for (auto& [v, w] : edge[u]) {
    if (vis[v] == 0) {
      dis[v] = dis[u] + w;
      if (dis[v] > dis[c]) {
        c = v;
      }
      dfs(v);
    }
  }
}

int main() {
  int n, u, v, w;
  cin >> n;
  vis.resize(n);
  dis.resize(n);
  edge.resize(n);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    --u, --v;  // 如果编号从1开始，减1使其变为 0-indexed
    edge[u].emplace_back(v, w);
    edge[v].emplace_back(u, w);
  }
  dfs(0);
  dis[c] = 0;
  vis.clear(), vis.resize(n);
  dfs(c);
  cout << dis[c] << endl;
  return 0;
}

树形 DP

我们记录当 0 为树的根时，每个节点作为子树的根向下，所能延伸的最远距离 $d_1$，和次远距离 $d_2$，那么直径就是所有 $d_1 + d_2$ 的最大值。

因为在确定树根的情况下， 直径一定会经过树根, 而每个节点都被当作树根进行过扫描

树形 DP 可以在存在负权边的情况下求解出树的直径。

如果需要求出一条直径上所有的节点，则可以在 DP 的过程中，记录下每个节点能向下延伸的最远距离与次远距离所对应的子节点，之后再找到对应的 $u$，使得 $d = d_1 u + d_2 u$，即可分别沿着从 $u$ 开始的最远距离和次远距离对应的子节点一路向下，遍历直径上所有的节点。

实现

#include <iostream>
#include <vector>
using namespace std;

vector<vector<pair<int, int>>> edge;
vector<int> dis1, dis2, vis;
int d = 0;

void dfs(int u) {
  vis[u] = 1;
  dis1[u] = dis2[u] = 0;
  for (auto& [v, w] : edge[u]) {
    if (vis[v] == 0) {
      dfs(v);
      int t = dis1[v] + w;
      if (t > dis1[u]) {
        dis2[u] = dis1[u];
        dis1[u] = t;
      } else if (t > dis2[u]) {
        dis2[u] = t;
      }
    }
  }
  d = max(d, dis1[u] + dis2[u]);
}

int main() {
  int n, u, v, w;
  cin >> n;
  dis1.resize(n);
  dis2.resize(n);
  vis.resize(n);
  edge.resize(n);
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    --u, --v;  // 如果编号从1开始，减1使其变为 0-indexed
    edge[u].emplace_back(v, w);
    edge[v].emplace_back(u, w);
  }
  dfs(0);
  cout << d << endl;
  return 0;
}

例题

洛谷U81904 树的直径 LC1245. 树的直径