#include #include using namespace std; #define MAXN (100000+1) #define MAXM (200000+1) int N, M; vector tree[MAXN]; int cost[MAXN]; int cost_sum[MAXN]; int depth[MAXN]; int log_n; vector > par; void dfs(int v, int p, int c, int d) { par[0][v] = p; depth[v] = d; cost_sum[v] = cost[v] + c; for (int i = 0; i < tree[v].size(); i++) { if (tree[v][i] != p) { dfs(tree[v][i], v, cost_sum[v], d+1); } } } void init() { while (N > (1 << log_n)) log_n++; par = vector >(log_n, vector(N)); dfs(0, -1, 0, 0); for (int k = 0; k < log_n-1; k++) { for(int v = 0; v < N; v++) { if (par[k][v] < 0) { par[k+1][v] = -1; } else { par[k+1][v] = par[k][par[k][v]]; } } } } int solve(int u, int v) { if (depth[u] > depth[v]) { swap(u, v); } for (int k = 0; k < log_n; k++) { if((depth[v] - depth[u]) >> k & 1)v = par[k][v]; } if(u==v)return u; for (int k = log_n-1; k >= 0; k--) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } return par[0][u]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int n = 0; n < (N-1); n++) { int a, b; cin >> a; cin >> b; tree[a].push_back(b); tree[b].push_back(a); } for (int n = 0; n < N; n++) { cin >> cost[n]; } init(); unsigned long long total = 0; cin >> M; for (int m = 0; m < M; m++) { int a, b, c, p; cin >> a; cin >> b; cin >> c; p = solve(a, b); total += (cost_sum[a] + cost_sum[b] - (cost_sum[p] * 2) + cost[p]) * c; } cout << total << endl; }