思路与算法

后序维护每个子树的加权直径两端，结合子直径和两条最深向下路径。子树中任一点最远距离等于到这两端距离的最大值。最优顶点在直径上，用LCA及二进制祖先定位直径长度一半两侧的相邻顶点，比较二者偏心距得到离散半径。

正确性说明

树上最远点性质保证直径端点决定所有点偏心距；直径外的顶点投影到直径后只会减小到两端距离，因此最优中心可在直径上。路径上目标为max(x,D-x)，距离中点越近越优，只需比较中点两侧顶点。后序合并完整枚举子直径及穿过根的候选。

复杂度

初始化、遍历O(N)，祖先表和各子树中心定位O(NlogN)，总O(NlogN)时间，O(NlogN)空间，使用扁平邻接与祖先表控制百万点内存。

易错点

边带权，顶点中心不能直接输出ceil(D/2)。单节点半径0。距离用64位，长链不能递归。中点可能位于长边内部，两个端点都要试。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> head(n, -1), to(2 * max(0, n - 1)), next(to.size()), wt(to.size());
    int ec = 0;
    auto add = [&](int a, int b, int w) {
        to[ec] = b;
        wt[ec] = w;
        next[ec] = head[a];
        head[a] = ec++;
    };
    for (int i = 1; i < n; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        add(--a, --b, w);
        add(b, a, w);
    }
    int K = 1;
    while ((1 << K) <= n)
        K++;
    vector<vector<int>> up(K, vector<int>(n));
    vector<int> par(n, -1), dep(n), ord(1, 0), downEnd(n), A(n), B(n);
    vector<long long> dist(n), down(n), diam(n);
    for (int i = 0; i < n; i++)
        A[i] = B[i] = downEnd[i] = i;
    for (size_t i = 0; i < ord.size(); i++) {
        int u = ord[i];
        for (int e = head[u]; e >= 0; e = next[e]) {
            int v = to[e];
            if (v == par[u])
                continue;
            par[v] = u;
            up[0][v] = u;
            dep[v] = dep[u] + 1;
            dist[v] = dist[u] + wt[e];
            ord.push_back(v);
        }
    }
    for (int k = 1; k < K; k++)
        for (int u = 0; u < n; u++)
            up[k][u] = up[k - 1][up[k - 1][u]];
    for (int i = n - 1; i >= 0; i--) {
        int u = ord[i];
        long long d1 = 0, d2 = 0;
        int e1 = u, e2 = u;
        for (int e = head[u]; e >= 0; e = next[e]) {
            int v = to[e];
            if (par[v] != u)
                continue;
            if (diam[v] > diam[u]) {
                diam[u] = diam[v];
                A[u] = A[v];
                B[u] = B[v];
            }
            long long d = down[v] + wt[e];
            if (d > d1) {
                d2 = d1;
                e2 = e1;
                d1 = d;
                e1 = downEnd[v];
            } else if (d > d2) {
                d2 = d;
                e2 = downEnd[v];
            }
        }
        down[u] = d1;
        downEnd[u] = e1;
        if (d1 + d2 > diam[u]) {
            diam[u] = d1 + d2;
            A[u] = e1;
            B[u] = e2;
        }
    }
    auto lca = [&](int a, int b) {
        if (dep[a] < dep[b])
            swap(a, b);
        for (int k = K - 1; k >= 0; k--)
            if ((dep[a] - dep[b]) >> k & 1)
                a = up[k][a];
        if (a != b) {
            for (int k = K - 1; k >= 0; k--)
                if (up[k][a] != up[k][b]) {
                    a = up[k][a];
                    b = up[k][b];
                }
            a = up[0][a];
        }
        return a;
    };
    for (int u = 0; u < n; u++) {
        int a = A[u], b = B[u], p = lca(a, b);
        long long D = diam[u];
        if (2 * (dist[a] - dist[p]) < D)
            swap(a, b);
        int v = a;
        for (int k = K - 1; k >= 0; k--) {
            int z = up[k][v];
            if (dep[z] >= dep[p] && 2 * (dist[a] - dist[z]) <= D)
                v = z;
        }
        long long from = dist[a] - dist[v];
        long long ans = max(from, D - from);
        if (v != p) {
            int z = par[v];
            long long t = dist[a] - dist[z];
            ans = min(ans, max(t, D - t));
        }
        cout << ans << '\n';
    }
}