#include using namespace std; using ll = long long; class heavy_light_decomposition { const int n; vector> g; vector par, head, in, out; void dfs1(int rt) { vector size(n, 1); vector iter(n); vector> stp; stp.reserve(n); stp.emplace_back(rt, -1); while (!stp.empty()) { int v = stp.back().first; if (iter[v] < g[v].size()) { if (g[v][iter[v]] != stp.back().second) { stp.emplace_back(g[v][iter[v]], v); } ++iter[v]; continue; } par[v] = stp.back().second; for (auto& u : g[v]) if (u == par[v]) { if (u != g[v].back()) swap(u, g[v].back()); g[v].pop_back(); break; } for (auto& u : g[v]) { size[v] += size[u]; if (size[u] > size[g[v].front()]) swap(u, g[v].front()); } stp.pop_back(); } } void dfs2(int rt) { int it = 0; vector iter(n); vector st; st.reserve(n); st.push_back(rt); while (!st.empty()) { int v = st.back(); if (!iter[v]) in[v] = it++; if (iter[v] < g[v].size()) { int u = g[v][iter[v]]; head[u] = iter[v] ? u : head[v]; st.push_back(u); ++iter[v]; continue; } out[v] = it; st.pop_back(); } } public: heavy_light_decomposition(int n_) : n(n_), g(n), par(n), head(n), in(n), out(n) {} heavy_light_decomposition(const vector>& G) : n(G.size()), g(G), par(n), head(n), in(n), out(n) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { dfs1(rt); head[rt] = rt; dfs2(rt); } int get_id(int v) { return in[v]; } void path_query(int u, int v, function f) { while (true) { if (in[u] > in[v]) swap(u, v); f(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) return; v = par[head[v]]; } } }; int main() { ios::sync_with_stdio(false), cin.tie(0); int N; cin >> N; heavy_light_decomposition hl(N); for (int i = 0; i < N - 1; i++) { int A, B; cin >> A >> B; hl.add_edge(A, B); } hl.build(); vector u(N), sum(N + 1); for (int i = 0; i < N; i++) { int U; cin >> U; u[hl.get_id(i)] = U; } for (int i = 0; i < N; i++) { sum[i + 1] = sum[i] + u[i]; } int M; cin >> M; ll res = 0; while (M--) { int A, B; ll C; cin >> A >> B >> C; ll all = 0; hl.path_query(A, B, [&](int l, int r) { all += sum[r] - sum[l]; }); res += all * C; } cout << res << endl; return 0; }