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 DisjointSet(object): def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def union(self, x, y): self._link(self.find_set(x), self.find_set(y)) def _link(self, x, y): if self.rank[x] > self.rank[y]: self.parent[y] = x else: self.parent[x] = y if self.rank[x] == self.rank[y]: self.rank[y] += 1 def find_set(self, x): xp = self.parent[x] if xp != x: self.parent[x] = self.find_set(xp) return self.parent[x] class Tree(object): 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.cost = Us self._set_child(Es) def _set_child(self, Es): que = [self.root] visited = [False] * self.n self.cum_cost[self.root] = self.cost[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 + self.cost[u] que.append(u) visited[v] = True class LCATarjan(object): def __init__(self, tree): self.n = tree.n self.root = tree.root self.child = tree.child self.ancestor = list(range(self.n)) self.visited = [False] * self.n self.ds = DisjointSet(self.n) self.lca = dict() def find(self, pairs): self._preprocess(pairs) self._LCA(self.root) return self.lca def _preprocess(self, pairs): self.pairs = [[] for node in range(self.n)] for u, v in pairs: self.pairs[u].append(v) self.pairs[v].append(u) def _LCA(self, u): self.ancestor[self.ds.find_set(u)] = u for v in self.child[u]: self._LCA(v) self.ds.union(u, v) self.ancestor[self.ds.find_set(u)] = u self.visited[u] = True for v in self.pairs[u]: if self.visited[v]: self.lca[u, v] = self.ancestor[self.ds.find_set(v)] self.lca[v, u] = self.lca[u, v] def solve(N, Es, Us, M, moves): tree = Tree(N, Es, 0, Us) pairs = [(a, b) for a, b, c in moves] lcat = LCATarjan(tree) lca = lcat.find(pairs) tax = 0 for a, b, c in moves: v = lca[a, b] tax += (tree.cum_cost[a] + tree.cum_cost[b] - tree.cum_cost[v] * 2 + Us[v]) * c return tax pars = read_data() print(solve(*pars))