#include #include #include #include #include #include using namespace std; typedef long long ll; vector > G[100000]; int N, M; ll U[100010]; int A[10], B[10], C[10]; class LCA { public: int V, logV; vector depth, len; vector > parent; LCA(int V) { this->V = V; logV = 0; while(V > (1LL << logV)) logV++; this->depth = vector(V); this->len = vector(V); this->parent = vector >(logV, vector(V)); } void init(int v, int par, int d, int l) { depth[v] = d; parent[0][v] = par; len[v] = l; for(int i = 0; i < (int)G[v].size(); i++) { int w = G[v][i].first; int lc = G[v][i].second; if(w == par) continue; init(w, v, d + 1, lc + l); } } void build() { for(int k = 0; k + 1 < logV; 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]]; } } } ll query(int u, int v) { if(depth[u] > depth[v]) swap(u, v); for(int k = 0; k < logV; k++) { if((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if(u == v) { return u; } for(int k = logV - 1; k >= 0; k--) { if(parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; ll sum[100010]; void dfs(int n, int p, ll s) { sum[n] = s + U[n]; for(pair c : G[n]) { if(c.first != p) dfs(c.first, n, s + U[n]); } } 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; G[a].push_back(make_pair(b, 1)); G[b].push_back(make_pair(a, 1)); } LCA lca(N); lca.init(0, -1, 0, 0); lca.build(); for(int i = 0; i < N; i++) { cin >> U[i]; } dfs(0, -1, 0); ll ans = 0; cin >> M; for(int i = 0; i < M; i++) { cin >> A[i] >> B[i] >> C[i]; int cp = lca.query(A[i], B[i]); ans += C[i] * (sum[A[i]] + sum[B[i]] - sum[cp] * 2 + U[cp]); } cout << ans << endl; }