#include using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define ALL(x) (x).begin(), (x).end() #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) #define fst first #define snd second typedef vector vi;typedef vector vvi;typedef pair pii;typedef vector vpii; typedef long long ll; vi U; vvi E; struct LCA { int H, W; vector > parent, tax; vector depth; // LCA(木の頂点数) LCA(int V, vector >& E) : W(V), depth(V) { H = 1; while (1 << H < W) H++; parent.resize(H, vector(W)); tax.resize(H, vector(W)); rep(i,V) tax[0][i] = U[i]; // 適当な頂点からdfsして親を求めておく dfs(E, 0, -1, 0); // 親をダブリングする for (int k = 1; k < H; k++) { for (int v = 0; v < W; v++) { parent[k][v] = parent[k-1][v] == -1 ? -1 : parent[k-1][parent[k-1][v]]; tax[k][v] = parent[k-1][v] == -1 ? tax[k-1][v] : (tax[k-1][v] + tax[k-1][parent[k-1][v]]); } } } void dfs(vector >& E, int cur, int par, int dep) { parent[0][cur] = par; depth[cur] = dep; for (int i = 0; i < (int) E[cur].size(); i++) { if (E[cur][i] != par) dfs(E, E[cur][i], cur, dep + 1); } } // u と v の LCA を求める int query(int u, int v) { // 深い方を v にしておく if (depth[u] > depth[v]) swap(u, v); // 根からの深さが u と同じになるまで v の親をたどる int ret = 0; for (int k = 0; k < H; k++) { if ((depth[v]-depth[u]) >> k & 1) { ret += tax[k][v]; v = parent[k][v]; } } if (u == v) return ret + tax[0][u]; // 二分探索でLCAを求める for (int k = H - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { ret += tax[k][u]; ret += tax[k][v]; u = parent[k][u]; v = parent[k][v]; } } return ret += tax[0][u] + tax[0][v] + tax[0][parent[0][u]]; } }; void Main() { int N; scanf("%d", &N); E.resize(N); rep(i,N-1) { int a, b; scanf("%d%d", &a, &b); E[a].push_back(b); E[b].push_back(a); } U.resize(N); rep(i, N) scanf("%d", &U[i]); LCA lca(N, E); ll ans = 0; int M; scanf("%d", &M); rep(i,M) { int a,b,c; scanf("%d%d%d", &a, &b, &c); int x = lca.query(a, b); //_p("(%d,%d):%d\n", a,b,x); ans += 1LL * x * c; } _p("%lld\n", ans); } int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }