树的直径与重心

// 适用于边权非负的树
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];
}

int diameter = 0;

// 返回以 u 为根的子树中，从 u 出发的最长路径
int dfs(int u, int parent, List<int[]>[] adj) {
    int max1 = 0, max2 = 0; // 最长和次长
    for (int[] edge : adj[u]) {
        int v = edge[0], w = edge[1];
        if (v == parent) continue;
        int d = dfs(v, u, adj) + w;
        if (d > max1) { max2 = max1; max1 = d; }
        else if (d > max2) { max2 = d; }
    }
    diameter = Math.max(diameter, max1 + max2); // 经过 u 的最长路径
    return max1;
}

int[] size;
int centroid = -1, minMaxPart = Integer.MAX_VALUE;

void findCentroid(int u, int parent, int n, List<Integer>[] adj) {
    size[u] = 1;
    int maxPart = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        findCentroid(v, u, n, adj);
        size[u] += size[v];
        maxPart = Math.max(maxPart, size[v]);
    }
    maxPart = Math.max(maxPart, n - size[u]); // 上方部分
    if (maxPart < minMaxPart) {
        minMaxPart = maxPart;
        centroid = u;
    }
}