max の場合に関する補足です。

貪欲に一番大きいパスを選ぶさい、公式解説では segment tree を持ち出していますが、DFS などで、葉から順番に貪欲に上にあげることをしても良いです。

適切に頂点番号をラベリングし直すことで、\(1\) を根としたとき、\(a\) の親が \(b\) であるとき、\(b < a\) が成り立つようにします。

そのとき、以下に表すようなアルゴリズムで答えを求めることができます。

add_cost = []
dp = [0] * N
for i in range(N - 1, -1, -1):
  # i が葉のとき、dp[i] は W[i] とする。
  if len(G[i]) == 0:
    dp[i] = W[i]
    continue
  # 子供がいるとき、dp が一番大きい子供を選び、そいつとのパスを繋ぐ
  # それ以外の頂点は後回しにする
  ind = -1  
  for ch in G[i]:
    if ind == -d:
      ind = ch
    elif dp[ind] < dp[ch]:
      add_cost.appned(dp[ind])
      ind = ch
    else:
      add_cost.appned(dp[ch])
  dp[i] = W[i] + dp[ind]
# 初期状態で最も極大なものは、dp[0] に格納されている
add_cost.append(dp[0])
add_cost.sort()
add_cost.reverse()
cost = 0
ans = 0
for a in add_cost:
  cost += a
  ans += cost
print(ans)

ABC の類題