#include #include #include #include #include #include using namespace std; typedef long long ll; const int kMAX_N = 100010; const int kMAX_M = 200010; const int kMAX_V = kMAX_N; const int kMAX_LOG_V = 20; struct LCA { int V; int root; vector graph[kMAX_V]; int parent[kMAX_LOG_V][kMAX_V]; int depth[kMAX_V]; LCA() { } void init(int v, int r) { V = v; root = r; DFS(root, -1, 0); for (int k = 0; k + 1 < kMAX_LOG_V; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void AddEdge(int from, int to) { graph[from].push_back(to); } void DFS(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int i = 0; i < graph[v].size(); i++) { if (graph[v][i] != p) DFS(graph[v][i], v, d + 1); } } int Solve(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < kMAX_LOG_V; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = kMAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; int N, M; LCA lca; int U[kMAX_N], cost[kMAX_N]; void DFS(int node, int par, int c) { cost[node] = c; for (int i = 0; i < lca.graph[node].size(); i++) { int to = lca.graph[node][i]; if (to != par && cost[to] < 0) { DFS(to, node, c + U[to]); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; lca.AddEdge(a, b); lca.AddEdge(b, a); } for (int i = 0; i < N; i++) { cin >> U[i]; } lca.init(N, 0); memset(cost, -1, sizeof(cost)); DFS(0, -1, U[0]); ll answer = 0; cin >> M; for (int i = 0; i < M; i++) { int a, b, c; cin >> a >> b >> c; int l = lca.Solve(a, b); ll road_cost = (ll)cost[a] + (ll)cost[b] - 2 * (ll)cost[l] + (ll)U[l]; answer += road_cost * c; } cout << answer << endl; return 0; }