1function bfs(start, adj) {
2 const dist = new Array(adj.length).fill(-1);
3 const q = [start]; dist[start] = 0;
4 for (let i = 0; i < q.length; i++)
5 for (const v of adj[q[i]])
6 if (dist[v] < 0) { dist[v] = dist[q[i]] + 1; q.push(v); }
7 let best = start;
8 for (let u = 0; u < adj.length; u++)
9 if (dist[u] > dist[best]) best = u;
10 return { best, dist };
11}
12// 直径：两次 BFS，先找最远点 p，再从 p 找最远点 q
13const p = bfs(0, adj).best;
14const { best: q, dist: d2 } = bfs(p, adj);
15const diameter = d2[q];
16// 重心：删除后使最大连通块最小的节点
17function dfs(u, fa) {
18 size[u] = 1; let maxPart = 0;
19 for (const v of adj[u]) {
20 if (v === fa) continue;
21 dfs(v, u); size[u] += size[v];
22 maxPart = Math.max(maxPart, size[v]);
23 }
24 maxPart = Math.max(maxPart, n - size[u]);
25 if (maxPart < bestMax) { bestMax = maxPart; centroid = u; }
26}