import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map.Entry; import java.util.StringTokenizer; public class Main { public static class UnionFind{ int[] par; // public UnionFind(int n){ par = new int[n]; for(int i = 0; i < n; i++){ par[i] = -1; } } public int find(int x){ if(par[x] < 0){ return x; }else{ return par[x] = find(par[x]); } } public boolean union(int x, int y){ x = find(x); y = find(y); if(x != y){ if(par[y] < par[x]) { // 多い方が根になるようにスワップする. int tmp = x; x = y; y = tmp; } par[x] += par[y]; par[y] = x; return true; }else{ return false; } } public boolean same(int x, int y){ return find(x) == find(y); } public int size(int x){ return -par[find(x)]; } } // DFS で 前順走査(preorder) で 一番近い親を探す. 部分木のマージに, UnionFind を使う . public static void dfs(ArrayList>> querys, int[] lcas, int node, int parent, boolean[] visited, int[] ancestor, ArrayList> adj, UnionFind uf) { ancestor[uf.find(node)] = node; // 自分の祖先は自分. for (final int next : adj.get(node)){ if(next == parent){ continue; } if(next == node){ continue; } dfs(querys, lcas, next, node, visited, ancestor, adj, uf); uf.union(node, next); // next以下のLCAを探索し終えたので, 部分木を併合. ancestor[uf.find(node)] = node; // 併合した祖先は自分(部分木内はもう終えてる) } visited[node] = true; for(final Entry> pair_entry : querys.get(node).entrySet()){ final int pair_node = pair_entry.getKey(); for(final int pair_index : pair_entry.getValue()){ if(visited[pair_node]){ lcas[pair_index] = ancestor[uf.find(pair_node)]; } } } } public static int[] offlineLCA(int[] us, int[] vs, ArrayList> adj) { final int n = adj.size(); int[] lca_nodes = new int[us.length], ancestor = new int[n]; boolean[] visited = new boolean[n]; UnionFind uf = new UnionFind(n); ArrayList>> querys = new ArrayList>>(); for(int i = 0; i < n; i++){ querys.add(new HashMap>()); } for(int i = 0; i < us.length; i++){ if(!querys.get(us[i]).containsKey(vs[i])){ querys.get(us[i]).put(vs[i], new HashSet()); } querys.get(us[i]).get(vs[i]).add(i); if(!querys.get(vs[i]).containsKey(us[i])){ querys.get(vs[i]).put(us[i], new HashSet()); } querys.get(vs[i]).get(us[i]).add(i); } dfs(querys, lca_nodes, 0, -1, visited, ancestor, adj, uf); return lca_nodes; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int N = sc.nextInt(); ArrayList> tree = new ArrayList>(); for(int i = 0; i < N; i++){ tree.add(new HashSet()); } for(int i = 0; i < N - 1; i++){ final int A = sc.nextInt(); final int B = sc.nextInt(); tree.get(A).add(B); tree.get(B).add(A); } long[] node_costs = new long[N]; for(int i = 0; i < N; i++){ node_costs[i] = sc.nextLong(); } long[] from_0_cost = new long[N]; LinkedList node_queue = new LinkedList(); LinkedList parent_queue = new LinkedList(); node_queue.add(0); parent_queue.add(-1); while(!node_queue.isEmpty()){ final int node = node_queue.poll(); final int parent = parent_queue.poll(); if(parent >= 0){ from_0_cost[node] += from_0_cost[parent]; } from_0_cost[node] += node_costs[node]; for(final int next : tree.get(node)){ if(next == parent){ continue; } if(next == node){ continue; } node_queue.add(next); parent_queue.add(node); } } final int M = sc.nextInt(); int[] as = new int[M]; int[] bs = new int[M]; long[] cs = new long[M]; for (int i = 0; i < M; i++) { final int A = sc.nextInt(); final int B = sc.nextInt(); final int C = sc.nextInt(); as[i] = A; bs[i] = B; cs[i] = C; } int[] lcas = offlineLCA(as, bs, tree); System.out.println("TEST"); long sum = 0; for(int i = 0; i < M; i++){ final long A_cost = from_0_cost[as[i]]; final long B_cost = from_0_cost[bs[i]]; final long lca_cost = from_0_cost[lcas[i]]; final long lca_node_cost = node_costs[lcas[i]]; //System.out.println(A_cost + " " + B_cost + " " + lca_cost + " " + lca_node_cost); //System.out.println(cs[i] * (A_cost + B_cost - 2 * lca_cost + lca_node_cost)); sum += cs[i] * (A_cost + B_cost - 2 * lca_cost + lca_node_cost); } System.out.println(sum); } public static class Scanner implements AutoCloseable { private BufferedReader br; private StringTokenizer tok; public Scanner(InputStream is) { br = new BufferedReader(new InputStreamReader(is)); } private void getLine() { try { while (!hasNext()) {tok = new StringTokenizer(br.readLine());} } catch(IOException e){ /* ignore */ } } private boolean hasNext() { return tok != null && tok.hasMoreTokens(); } public String next() { getLine(); return tok.nextToken(); } public int nextInt(){ return Integer.parseInt(next()); } public long nextLong(){ return Long.parseLong(next()); } public void close() { try{ br.close(); } catch (IOException e){ /*ignore*/ } } } }