package yukicoder; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solver(); } @SuppressWarnings("unchecked") void solver() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); edges = new ArrayList[N]; for (int i = 0; i < N; i++) { edges[i] = new ArrayList<>(); } for (int i = 0; i < N - 1; i++) { int a = sc.nextInt(); int b = sc.nextInt(); edges[a].add(b); edges[b].add(a); } init(N); int[] u = new int[N]; for (int i = 0; i < N; i++) { u[i] = sc.nextInt(); } init2(u); int M = sc.nextInt(); long ans = 0; for (int i = 0; i < M; i++) { int f = sc.nextInt(); int t = sc.nextInt(); int c = sc.nextInt(); int lca = lca(f, t); int ret = cost(lca, f) + cost(lca, t) - u[lca]; ans += ret * c; } System.out.println(ans); } int MAX_LOG_V;// =(int)log2(MAX_V)+1 int MAX_V; int root;// 根ノードの番号 int parent[][];// [MAX_LOG_V + 1][MAX_V] // parent[k][v] 2^k回親を辿ったときに到達する頂点(根を通り過ぎたときは-1) int[] depth;// [MAX_V] 根からの深さ ArrayList edges[]; void init(int N) { // 変数の用意 MAX_V = N; MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1; root = 0; parent = new int[MAX_LOG_V + 1][MAX_V]; depth = new int[MAX_V]; cost = new int[MAX_LOG_V + 1][MAX_V];// cost[k][v] // 頂点vから(2^k-1)回親を辿ったときにかかるお金 // parent[0]とdepthを初期化する bfs(root, -1, 0); // parentを初期化する for (int k = 0; k < MAX_LOG_V; k++) { for (int v = 0; v < MAX_V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } class P { int parent; int me; int depth; P(int me, int parent, int depth) { this.me = me; this.parent = parent; this.depth = depth; } } // dfsだとstack over flow が怖いのでbfs void bfs(int v, int p, int d) { ArrayDeque

q = new ArrayDeque

(); q.add(new P(v, p, d)); while (!q.isEmpty()) { P u = q.poll(); parent[0][u.me] = u.parent; depth[u.me] = u.depth; for (int i = 0; i < edges[u.me].size(); i++) { if (edges[u.me].get(i) != u.parent) q.add(new P(edges[u.me].get(i), u.me, u.depth + 1)); } } } int lca(int u, int v) { // uとvの深さが同じになるまで親を辿る if (depth[u] > depth[v]) { int d = u; u = v; v = d; } // depth[v]-depth[u]>=2^kとなる最小のkを求める。 // つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。 for (int k = 0; k < MAX_LOG_V; k++) { if ((((depth[v] - depth[u]) >> k) & 1) == 1) { v = parent[k][v]; } } if (u == v) return u; // uとvが衝突しないように辿る。 for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int[][] cost;// cost[k][v] 頂点vから(2^k-1)回親を辿ったときにかかるお金 void init2(int[] u) { // cost[0][v]を初期化する for (int i = 0; i < MAX_V; i++) { cost[0][i] = u[i]; } // parentを初期化する for (int k = 0; k < MAX_LOG_V; k++) { for (int v = 0; v < MAX_V; v++) { if (parent[k][v] == -1) { cost[k + 1][v] = Integer.MAX_VALUE / 4; } else { cost[k + 1][v] = cost[k][parent[k][v]] + cost[k][v]; } } } } int cost(int c, int p) { if (depth[c] < depth[p]) { int d = c; c = p; p = d; } int d = depth[c] - depth[p] + 1; int sum = 0; for (int i = 0; d > 0; d >>= 1, i++) { if ((d & 1) == 1) { sum += cost[i][c]; if (cost[i][c] >= Integer.MAX_VALUE / 4) throw new AssertionError("error"); if (parent[i][c] != -1) { c = parent[i][c]; } } } return sum; } void tr(Object...o){System.out.println(Arrays.deepToString(o));} }