#include #include #include #include using namespace std; typedef unsigned long long INT; #define MAXN (100000+1) #define MAXM (200000+1) struct Root { int no; int cost; vector roots; }; INT N, M, TOTAL; Root R[MAXN]; INT memo[MAXN]; bitset bit; INT fn(INT a, INT b, INT c) { if (memo[a] > 0) { return memo[a]; } INT rc; if (a == b) { rc = R[a].cost * c; } else { rc = -1; for (INT n = 0; n < R[a].roots.size(); n++) { if (bit.test(R[a].roots[n]) == 0) { bit.set(R[a].roots[n]); rc = min(rc, fn(R[a].roots[n], b, c)); bit.reset(R[a].roots[n]); } } if (rc != -1) { rc += (R[a].cost * c); } } return memo[a] = rc; } int main() { TOTAL = 0; cin >> N; for (INT n = 0; n < (N-1); n++) { INT A, B; cin >> A; cin >> B; R[A].roots.push_back(B); R[B].roots.push_back(A); } for (INT n = 0; n < N; n++) { R[n].no = n; cin >> R[n].cost; } cin >> M; for (INT m = 0; m < M; m++) { INT A, B, C; cin >> A; cin >> B; cin >> C; bit = 0; memset(memo, 0, sizeof(memo)); TOTAL += fn(A, B, C); } cout << TOTAL << endl; }