There are two ways to solve this problem. We will introduce them in the following order:

1. Solution using diameter
2. Solution using rerooting DP (Dynamic Programming)

1. Solution using diameter

In the following explanation, for a pair of vertices \((s,t)\) of an undirected graph, we denote by \(d(s,t)\) the distance (the length of shortest path) between \(s\) and \(t\).

The diameter is the distance between the most distant pair of vertices. Formally, it is the maximum value of \(d(s,t)\) for pairs of vertices \((s,t)\).

Let \((s,t)\) be a pair of vertices with their distance equal to the diameter. Then, for every vertex in the graph, the following property holds:

For every vertex \(u\) in the graph, one of the furthest vertex from \(u\) is either \(s\) or \(t\). In other words,

\[\max_{v \in G} d(u,v) = \max(d(u,s), d(u,t)).\]

With the property of the diameter, this problem can be solved as follows.

Let us denote the given graph by \(G(V,E)\). (\(V\) denotes the set of vertices and \(E\) of edges.)
We consider a new extend graph which has, for every vertex \(v \in V\), an additional auxiliary node \(v'\), connected with \(v\) by an edge of weight \(D_v\).

The following diagram illustrates the extended graph of Sample 1.

What we want is

\[ \max (\max_{u \in V, u \neq v} d(v,u') ) \ \cdots (\ast)\]

for every \(v \in V\), but this is equal to

\[ (\ast) = \begin{cases} d(v, t') & v = s \\ d(v, s') & v = t \\ \max(d(v,s'),d(v,t')) & \mathrm{otherwise,} \end{cases} \]

where \(s'\) and \(t'\) is a pair of vertices whose distance is equal to the diameter of the extended graph, obtained by computing the extended graph.

The diameter can be computed by applying Dijkstra’s algorithm twice. Therefore, the problem has been solved in a total of \(\mathrm{O}(N \log N)\) time.

A sample code in C++ follows.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)

struct E {
  int u, v, cost;
};
vector<vector<E>> g;

vector<ll> dijkstra(int start = 0) {
  int N = g.size();
  vector<ll> d(N, 1e18);
  using P = pair<ll, int>;
  priority_queue<P, vector<P>, greater<P>> Q;

  Q.emplace(0, start);
  d[start] = 0;

  while (!Q.empty()) {
    auto [dc, c] = Q.top();
    Q.pop();
    if (d[c] != dc) continue;
    for (auto& e : g[c]) {
      ll dist = dc + e.cost;
      if (dist < d[e.v]) {
        d[e.v] = dist;
        Q.emplace(dist, e.v);
      }
    }
  }

  return d;
}

int main() {
  int N;
  cin >> N;
  g.resize(N);
  rep(i, N - 1) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a].push_back(E{a, b, c});
    g[b].push_back(E{b, a, c});
  }
  vector<ll> D(N);
  for (auto& x : D) cin >> x;

  // Find the diameter
  int s = 0, t = -1, u = -1;

  {
    auto ds = dijkstra(s);
    // Which is the furthest node?
    ll cost = -1;
    rep(i, N) {
      if (i == s) continue;
      if (D[i] + ds[i] > cost) {
        cost = D[i] + ds[i];
        t = i;
      }
    }
  }

  {
    auto dt = dijkstra(t);
    // Which is the furthest node?
    ll cost = -1;
    rep(i, N) {
      if (i == t) continue;
      if (D[i] + dt[i] > cost) {
        cost = D[i] + dt[i];
        u = i;
      }
    }
  }

  // Distance between t and u is equal to the diameter
  auto dt = dijkstra(t);
  auto du = dijkstra(u);
  rep(i, N) {
    ll cost = -1;
    if (i != t) cost = max(cost, dt[i] + D[t]);
    if (i != u) cost = max(cost, du[i] + D[u]);
    cout << cost << "\n";
  }
}

Solution using rerooting DP

This problem can be solved with an algorithm called rerooting DP.

There is a very famous editorials of rerooting in the article written by ei13333 (in Japanese). We recommend you to read this article first if you do not know what algorithm “rerooting DP” is.

Here we describe the algorithm briefly. First, consider the given graph as a rooted tree with root \(0\). Let \(m_i\)

• \(m_i:=\) maximum expense of travel from Vertex \(i\) to any vertex in the subtree rooted at \(i\).

This can be computed with the following DP.

# c:Current vertex p:Parent vertex
def dfs(c, p):
  dist = 0
  for d in (children of c):
    dfs(d, c)
    dist = max(D[d] + m[d]) + (cost of path c-d)
  d[c] = dist
  return

Next, we do rerooting using the results of precalculation to obtain

• \(dp_i ;=\) the answer for Vertex \(i\).

# c:Current vertex p:Parent vertex
# v:the contribution from the subtree rooted at the parent vertex when the tree is rooted at c
def dfs2(c, p, v):
  mc = [max(m[d], D[d]) + (cost of edge d-c) for d in (chlidren of c)]
  dp[c] = max(v, max(mc))
  for d in (children of c):
    # Eliminate the contribution from the subtree rooted at d
    exc_d = set(children of c) - d
    mc2 = [max(m[d], D[d]) + (cost of edge d-c) for d in exc_d]
    dv = max(v, max(mc2))
    dfs2(d, c, max(dv, D[c]) + (cost of edge d-c))
  return

If we implement the second DFS (Depth-First Search) just as described, it costs \(\mathrm{O}(N^2)\) time; however, if we use data structures like cumulative sums, the complexity is reduced to \(\mathrm{O}(N)\). Thus, the problem has been solved in a total of \(\mathrm{O}(N)\) time.

The sample code has an abstracted implementation of rerooting DP. The “abstraction” in competitive programming refers to creating a library that the algorithm works when functions and variables are supplied, so that the algorithm part can be black-boxed during the contest.

The main motivation of abstraction is to get AC as fast as possible by skipping some implementation during the contest with the aid of libraries. Using as an example problems solved by rerooting DP, in most cases, these four elements:

• the type of value that DP table stores
• the function for merging vertices, and its identity element
• the function returning a value to its parent
• the value when the child has no vertex (which is equal to the identity element in this problem)

differs problem to problem, while the other can be implemented in the same way regardless of the problem in order to solve it. So, if we have a library that calculates rerooting DP automatically when the four parameters above are given, we can indeed get AC fast.

One of the example of abstraction in competitive programming is Segment Tree in AtCoder Library. The document describes the usage in detail, so it is recommended to read it as an example of abstraction of algorithms.

However, most problems of AtCoder do not require a plethora of implementation, so preparing libraries does not contribute to the rating so much. Also, constructing abstracted libraries is often more difficult than solving problems during contests.

For these reasons, this may not be a good way of training of competitive programming, but personally I think it is one choice of deepening understanding of algorithm and programming languages.

The following is a sample implementation of abstracted rerooting DP and the answer for this problem in C++.

#include <iostream>
#include <vector>
using namespace std;

template <typename Cost>
struct Edge {
  int src, to;
  Cost cost;
  Edge(int s, int t, Cost c = 1) : src(s), to(t), cost(c) {}
  operator int() const { return to; }
};
template <typename Cost>
struct Graph : vector<vector<Edge<Cost>>> {
  Graph(int n) : vector<vector<Edge<Cost>>>(n) {}
  void add_edge(int s, int t, Cost c = 1) { (*this)[s].emplace_back(s, t, c); }
};

template <typename Cost, typename Data, Data (*merge)(Data, Data), Data (*e)(),
          Data (*leaf)(), Data (*apply)(Data, int, int, Cost)>
struct Rerooting : Graph<Cost> {
  vector<Data> dp, memo;

  Rerooting(int n) : Graph<Cost>::Graph(n) {}

  vector<Data> run() {
    memo.resize((*this).size(), e());
    dp.resize((*this).size());
    dfs1(0, -1);
    dfs2(0, -1, e());
    return dp;
  }

  void dfs1(int c, int p) {
    bool upd = false;
    for (Edge<Cost> &d : (*this)[c]) {
      if (d == p) continue;
      dfs1(d, c);
      upd = true;
      memo[c] = merge(memo[c], apply(memo[d], d, c, d.cost));
    }
    if (!upd) memo[c] = leaf();
  }

  void dfs2(int c, int p, const Data &val) {
    vector<Data> ds{val};
    for (Edge<Cost> &d : (*this)[c]) {
      if (d == p) continue;
      ds.push_back(apply(memo[d], d, c, d.cost));
    }
    int n = ds.size(), idx = 1;
    vector<Data> head(n + 1, e()), tail(n + 1, e());
    for (int i = 0; i++ < n;) head[i] = merge(head[i - 1], ds[i - 1]);
    for (int i = n; i-- > 0;) tail[i] = merge(tail[i + 1], ds[i]);
    dp[c] = head[n];
    for (Edge<Cost> &d : (*this)[c]) {
      if (d == p) continue;
      Data sub = merge(head[idx], tail[idx + 1]);
      dfs2(d, c, apply(sub, c, d, d.cost));
      idx++;
    }
  }
};

vector<int> D;

using Data = long long;
using Cost = long long;
Data merge(Data a, Data b) { return max(a, b); }
Data e() { return 0; }
Data leaf() { return 0; }
Data apply(Data a, int c, int, Cost w) { return max<Data>(a, D[c]) + w; }

int main() {
  int N;
  cin >> N;
  Rerooting<Cost, Data, merge, e, leaf, apply> g(N);
  for (int i = 0; i < N - 1; i++) {
    int s, t, c;
    cin >> s >> t >> c;
    g.add_edge(s - 1, t - 1, c);
    g.add_edge(t - 1, s - 1, c);
  }
  D.resize(N);
  for (auto &x : D) cin >> x;
  auto ans = g.run();
  for (auto &x : ans) cout << x << "\n";
}