#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define rep(i,n) for(int i=0; i pi; typedef pair pl; typedef pair plc; #define MAX_N 100100 #define MAX_LOG_N 30 int N, root; ll ans; vector g[MAX_N]; int depth[MAX_N]; int par[MAX_N][MAX_LOG_N]; int U[MAX_N * 2]; int sum[100100]; void bfs() { queue q; sum[0] = U[0]; q.push(0); while (!q.empty()) { int i = q.front(); q.pop(); for (int j : g[i])if (sum[j] == 0) { sum[j] = sum[i] + U[j]; q.push(j); } } } void dfs(int v, int p, int d) { par[v][0] = p; depth[v] = d; for (int i = 0; i < g[v].size(); i++) { if (g[v][i] == p)continue; dfs(g[v][i], v, d + 1); } } void fill_table() { for (int i = 0; i < 30-1; i++) { for (int j = 0; j < N; j++) { if (par[j][i] == -1)par[j][i + 1] = -1; else par[j][i + 1] = par[par[j][i]][i]; } } } int lca(int u, int v) { int tmp_u = u, tmp_v = v; if (depth[u] > depth[v])swap(u, v); for (int i = 19; i >= 0; i--) { if (((depth[v] - depth[u]) >> i) & 1) { v = par[v][i]; } } if (u == v)return u; for (int i = 19; i >= 0; i--) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } int main() { int q; cin >> N; rep(i, N-1) { int x, y; cin >> x >> y; g[x].push_back(y); g[y].push_back(x); } root = 0; dfs(root, -1, 0); fill_table(); rep(i, N)cin >> U[i]; bfs(); cin >> q; rep(i, q) { int u, v,c; cin >> u >> v >> c; int p = lca(u, v); ans += (sum[u] + sum[v] - sum[p] * 2 + U[p]) * c; } cout << ans << endl; return 0; }