#include using namespace std; using ll = long long; class HLDecomposition { vector> g; vector vid, head, heavy, parent, depth, inv; int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0; for (int next : g[curr]) if (next != prev) { depth[next] = depth[curr] + 1; int sub_next = dfs(next, curr); sub += sub_next; if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; } return sub; } void bfs() { int k = 0; queue q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { vid[i] = k++; inv[vid[i]] = i; head[i] = h; for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j); } } } public: HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {} void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); } void for_each(int u, int v, function f) { if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) for_each(u, parent[head[v]], f); } void for_each_directed(int u, int v, function f) { if (vid[u] > vid[v]) { f(max(vid[head[u]], vid[v]), vid[u], 1); if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f); } else { f(max(vid[head[v]], vid[u]), vid[v], 0); if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f); } } void for_each_edge(int u, int v, function f) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { f(vid[head[v]], vid[v]); for_each_edge(u, parent[head[v]], f); } else { if (u != v) f(vid[u] + 1, vid[v]); } } int ancestor(int u, int d) { while (true) { if (depth[head[u]] > depth[u] - d) { d -= depth[u] - depth[head[u]] + 1; if (head[u] == 0) return 0; u = parent[head[u]]; } else { return inv[vid[u] - d]; } } } int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; return lca(u, parent[head[v]]); } int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } }; template class SegmentTree { using func_t = function; const int n; const T id; func_t merge; vector data; int size(int n) { int res; for (res = 1; res < n; res <<= 1); return res; } T sub(int l, int r, int node, int lb, int ub) { if (ub <= l || r <= lb) return id; if (l <= lb && ub <= r) return data[node]; return merge(sub(l, r, node * 2, lb, (lb + ub) / 2), sub(l, r, node * 2 + 1, (lb + ub) / 2, ub)); } public: SegmentTree(int n_, T id_, func_t merge_) : n(size(n_)), id(id_), merge(merge_), data(size(n_) * 2, id_) {} void Init(const vector& data_) { for (int i = 0; i < (int)data_.size(); i++) data[i + n] = data_[i]; for (int i = n - 1; i >= 0; i--) data[i] = merge(data[i * 2], data[i * 2 + 1]); } void Update(int p, T val) { p += n; data[p] = val; while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]); } void Add(int p, T val) { p += n; data[p] += val; while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]); } T Find(int i) { return data[i + n]; } T Find(int l, int r) { return sub(l, r + 1, 1, 0, n); } }; int main() { cin.sync_with_stdio(false); int N, M; cin >> N; HLDecomposition hl(N); for (int i = 0, A, B; i < N - 1; i++) { cin >> A >> B; hl.add(A, B); } hl.build(); SegmentTree st(N, 0, [](ll l, ll r) { return l + r; }); for (int i = 0, U; i < N; i++) { cin >> U; hl.for_each(i, i, [&](int l, int r) { st.Add(l, U); }); } cin >> M; ll res = 0; for (int i = 0, A, B, C; i < M; i++) { cin >> A >> B >> C; ll tmp = 0; hl.for_each(A, B, [&](int l, int r) { tmp += st.Find(l, r); }); res += tmp * C; } cout << res << endl; return 0; }