#include #include #include using namespace std; using UnWeightedGraph = vector>; struct LowestCommonAncestor { const UnWeightedGraph &g; int root; vector> parent; // parent[k][v] := 2^k-th parent of v vector depth; LowestCommonAncestor(const UnWeightedGraph &g, int r = 0) : \ g(g), root(r), depth(g.size()) { } void build() { int V = g.size(); int h = 1; while ((1 << h) < V) ++h; // 32 - __builtin_clz(V) parent.assign(h, vector(V, -1)); dfs(root, -1, 0); for (int k = 0; k + 1 < h; ++k) for (int v = 0; v < V; ++v) { if (parent[k][v] != -1) parent[k + 1][v] = parent[k][parent[k][v]]; } } void dfs(int u, int p, int d) { parent[0][u] = p; depth[u] = d; for (auto v: g[u]) if (v != p) dfs(v, u, d + 1); } int get(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < parent.size(); ++k) { if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; } if (u == v) return u; for (int k = parent.size() - 1; k >= 0; --k) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - depth[get(u, v)] * 2; } }; vector cost, acc; void rec(const UnWeightedGraph &g, int u, int p, int c) { acc[u] = c + cost[u]; for (auto v: g[u]) if (v != p) { rec(g, v, u, acc[u]); } } int main() { int N; cin >> N; UnWeightedGraph g(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } LowestCommonAncestor lca(g); lca.build(); cost.resize(N); acc.resize(N); for (auto &ci: cost) cin >> ci; rec(g, 0, -1, 0); long long res = 0; int Q; cin >> Q; while (Q--) { int a, b, c; cin >> a >> b >> c; int p = lca.get(a, b); res += (acc[a] + acc[b] - acc[p] * 2 + cost[p]) * c; } cout << res << endl; return 0; }