import sys import math sys.setrecursionlimit(10**6) input = raw_input range = xrange def read_data(): N = int(input()) Es = [[] for i in range(N)] for i in range(N - 1): a, b = map(int, input().split()) Es[a].append(b) Es[b].append(a) Us = [int(input()) for i in range(N)] M = int(input()) moves = [list(map(int, input().split())) for m in range(M)] return N, Es, Us, M, moves class Tree(): def __init__(self, N, Es, root, Us): self.n = N self.root = root self.child = [[] for i in range(N)] self.cum_cost = [0 for i in range(N)] self._set_child(Es, Us) def _set_child(self, Es, Us): que = [self.root] visited = [False] * self.n self.cum_cost[self.root] = Us[self.root] while que: v = que.pop() cum_cost_v = self.cum_cost[v] for u in Es[v]: if visited[u]: continue self.child[v].append(u) self.cum_cost[u] = cum_cost_v + Us[u] que.append(u) visited[v] = True class LCArmq(): def __init__(self, tree): D, E, R = self._convert_to_RMQ(tree.child, tree.root, tree.n) self._euler = E self._reverse = R self._RMQ = RMQ(D) def _convert_to_RMQ(self, child, root, n): ''' LCA の前処理。 RMQ に置き換えるため、Euler tour で巡回して深さのリストをつくる。 ''' depth = [] euler = [] reverse = [0] * n def euler_tour(node, d, depth, euler): for v in child[node]: euler.append(node) depth.append(d) euler_tour(v, d + 1, depth, euler) euler.append(node) depth.append(d) euler_tour(root, 0, depth, euler) for i, node in enumerate(euler): reverse[node] = i return depth, euler, reverse def query(self, v, w): i, j = self._reverse[v], self._reverse[w] rmq = self._RMQ.query(i, j) lca = self._euler[rmq] return lca class RMQ(): def __init__(self, A): self._A = A self._preprocess() def _preprocess(self): ''' RMQ の前処理。 ''' n = len(self._A) max_j = int(math.log(n, 2)) self._M = [list(range(n))] for j in range(0, max_j): shift = 1 << j Mj = self._M[j] Mjnext = [] for k1, k2 in zip(Mj, Mj[shift:]): k = k1 if self._A[k1] < self._A[k2] else k2 Mjnext.append(k) self._M.append(Mjnext) def query(self, i, j): if i == j: return i if i > j: i, j = j, i el = int(math.log(j - i, 2)) k1 = self._M[el][i] k2 = self._M[el][j - (1 << el) + 1] rmq = k1 if self._A[k1] < self._A[k2] else k2 return rmq def solve(N, Es, Us, M, moves): tree = Tree(N, Es, 0, Us) cum_cost = tree.cum_cost lca_rmq = LCArmq(tree) tax = 0 for a, b, c in moves: v = lca_rmq.query(a, b) tax += (cum_cost[a] + cum_cost[b] - cum_cost[v] * 2 + Us[v]) * c return tax pars = read_data() print(solve(*pars))