树的直径是树上最远两点的距离，树的重心是删除后使最大连通分量最小的点。两者都是树形 DP 的经典应用。
一、树的直径
定义
树上任意两点间距离的最大值。
方法一：两次 BFS/DFS
- 从任意点出发，找到最远点 u
- 从 u 出发，找到最远点 v
- dist(u, v) = 直径
// 适用于边权非负的树
int[] bfs(int start, List<int[]>[] adj) {
int n = adj.length;
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[start] = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(start);
while (!q.isEmpty()) {
int u = q.poll();
for (int[] edge : adj[u]) {
int v = edge[0], w = edge[1];
if (dist[v] == -1) {
dist[v] = dist[u] + w;
q.offer(v);
}
}
}
return dist;
}
// 求直径
int treeDiameter(List<int[]>[] adj) {
int[] d1 = bfs(0, adj);
int u = maxIndex(d1);
int[] d2 = bfs(u, adj);
int v = maxIndex(d2);
return d2[v];
}