板子题，模拟赛场切了。

思路

线段树换根板子题。

因为需要求每一个点的答案，所以定义 \(dp_i\) 表示以 \(i\) 为根的最长距离。

考虑将一个点 \(v\) 转化为根，树的形态会发生什么变化（假设 \(v\) 的父亲节点是 \(u\)）。

发现在 \(v\) 子树中的节点，距离都会减少 \(w_{u \to v}\)，其它节点都会加 \(w_{u \to v}\)。这个变化显然是可以将 DFS 序剖出来，然后用线段树优化的。

因为不能选择自己作为终点，所以查询最大值的时候避开即可。

Code

#include <bits/stdc++.h>  
#define re register  
#define int long long  
  
using namespace std;  
  
const int N = 2e5 + 10,M = 4e5 + 10;  
int n;  
int dp[N];  
int idx,h[N],ne[M],e[M],w[M],p[N];  
int num,f[N],d[N],sz[N],wson[N],id[N],tp[N];  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline void add(int a,int b,int c){  
    ne[idx] = h[a];  
    e[idx] = b;  
    w[idx] = c;  
    h[a] = idx++;  
}  
  
struct chain{  
    #define ls(u) (u << 1)  
    #define rs(u) (u << 1 | 1)  
  
    struct node{  
        int l,r;  
        int Max,tag;  
    }tr[N << 2];  
  
    inline void calc(int u,int k){  
        tr[u].Max += k;  
        tr[u].tag += k;  
    }  
  
    inline void pushup(int u){  
        tr[u].Max = max(tr[ls(u)].Max,tr[rs(u)].Max);  
    }  
  
    inline void pushdown(int u){  
        if (tr[u].tag){  
            calc(ls(u),tr[u].tag);  
            calc(rs(u),tr[u].tag);  
            tr[u].tag = 0;  
        }  
    }  
  
    inline void build(int u,int l,int r){  
        tr[u] = {l,r};  
        if (l == r) return;  
        int mid = l + r >> 1;  
        build(ls(u),l,mid);  
        build(rs(u),mid + 1,r);  
        pushup(u);  
    }  
  
    inline void modify(int u,int l,int r,int k){  
        if (l <= tr[u].l && tr[u].r <= r){  
            calc(u,k);  
            return;  
        }  
        pushdown(u);  
        int mid = tr[u].l + tr[u].r >> 1;  
        if (l <= mid) modify(ls(u),l,r,k);  
        if (r > mid) modify(rs(u),l,r,k);  
        pushup(u);  
    }  
  
    inline int query(int u,int l,int r){  
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].Max;  
        pushdown(u);  
        int res = 0;  
        int mid = tr[u].l + tr[u].r >> 1;  
        if (l <= mid) res = max(res,query(ls(u),l,r));  
        if (r > mid) res = max(res,query(rs(u),l,r));  
        return res;  
    }  
  
    inline void modify_node(int x,int k){  
        modify(1,id[x],id[x],k);  
    }  
  
    inline void modify_tree(int x,int k){  
        modify(1,id[x],id[x] + sz[x] - 1,k);  
    }  
  
    inline int query_sec(int l,int r){  
        if (l > r) return 0;  
        return query(1,l,r);  
    }  
  
    #undef ls  
    #undef rs  
}tree;  
  
inline void dfs1(int u,int fa){  
    sz[u] = 1;  
    f[u] = fa;  
    d[u] = d[fa] + 1;  
    for (re int i = h[u];~i;i = ne[i]){  
        int j = e[i];  
        if (j == fa) continue;  
        dfs1(j,u);  
        if (sz[j] > sz[wson[u]]) wson[u] = j;  
        sz[u] += sz[j];  
    }  
}  
  
inline void dfs2(int u,int fa,int top){  
    num++;  
    id[u] = num;  
    tp[u] = top;  
    if (!wson[u]) return;  
    dfs2(wson[u],u,top);  
    for (re int i = h[u];~i;i = ne[i]){  
        int j = e[i];  
        if (j == fa || j == wson[u]) continue;  
        dfs2(j,u,j);  
    }  
}  
  
inline void dfs_val(int u,int fa,int d){  
    tree.modify_node(u,d + p[u]);  
    for (re int i = h[u];~i;i = ne[i]){  
        int j = e[i];  
        if (j == fa) continue;  
        dfs_val(j,u,d + w[i]);  
    }  
}  
  
inline void dfs_get(int u,int fa){  
    for (re int i = h[u];~i;i = ne[i]){  
        int j = e[i];  
        if (j == fa) continue;  
        tree.modify_tree(1,w[i]);  
        tree.modify_tree(j,-2 * w[i]);  
        dp[j] = max(tree.query_sec(1,id[j] - 1),tree.query_sec(id[j] + 1,n));  
        dfs_get(j,u);  
        tree.modify_tree(1,-w[i]);  
        tree.modify_tree(j,2 * w[i]);  
    }  
}  
  
signed main(){  
    memset(h,-1,sizeof(h));  
    n = read();  
    for (re int i = 1;i < n;i++){  
        int a,b,c;  
        a = read();  
        b = read();  
        c = read();  
        add(a,b,c);  
        add(b,a,c);  
    }  
    for (re int i = 1;i <= n;i++) p[i] = read();  
    dfs1(1,0);  
    dfs2(1,0,1);  
    tree.build(1,1,n);  
    dfs_val(1,0,0);  
    dp[1] = max(tree.query_sec(1,id[1] - 1),tree.query_sec(id[1] + 1,n));  
    dfs_get(1,0);  
    for (re int i = 1;i <= n;i++) printf("%lld\n",dp[i]);  
    return 0;  
}