#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 500000; typedef pair S; struct Node { int v; int depth; Node(int v = -1, int depth = -1) { this->v = v; this->depth = depth; } bool operator<(const Node &n) const { return depth < n.depth; } }; class StaticRMQ { public: vector dat; int N; void init(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; ++i) { dat.push_back(Node(-1, MAX_V)); } } void update(int k, Node a) { k += N - 1; dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } ll find_min(int l, int r) { return query(l, r, 0, 0, N).v; } private: Node query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return Node(-1, MAX_V); if (a <= l && r <= b) { return dat[k]; } else { Node vl = query(a, b, k * 2 + 1, l, (l + r) / 2); Node vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } }; class LCA { public: vector vs; vector depth; vector id; vector > G; StaticRMQ rmq; LCA(int N, int root, vector > _G) { G = _G; int k = 0; vs = vector(2 * N - 1); depth = vector(2 * N - 1); id = vector(N, -1); dfs(root, -1, 0, k); rmq.init(k); for (int i = 0; i < k; ++i) { rmq.update(i, Node(vs[i], depth[i])); } } int find_parent(int u, int v) { return rmq.find_min(min(id[u], id[v]), max(id[u], id[v])); } private: void dfs(int v, int p, int d, int &k) { id[v] = k; vs[k] = v; depth[k++] = d; for (int i = 0; i < G[v].size(); ++i) { if (G[v][i] != p) { dfs(G[v][i], v, d + 1, k); vs[k] = v; depth[k++] = d; } } } }; int main() { int N; cin >> N; vector > G(N); int a, b; for (int i = 0; i < N - 1; ++i) { cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } vector U(N); for (int i = 0; i < N; ++i) { cin >> U[i]; } int root = 0; ll cost[N]; queue que; que.push(S(root, U[root])); bool visited[N]; memset(visited, false, sizeof(visited)); while (not que.empty()) { S s = que.front(); que.pop(); if (visited[s.first]) continue; visited[s.first] = true; cost[s.first] = s.second; for (int u : G[s.first]) { que.push(S(u, s.second + U[u])); } } LCA lca(N, root, G); int M; cin >> M; int l, r, c; ll total_cost = 0; for (int i = 0; i < M; ++i) { cin >> l >> r >> c; int p = lca.find_parent(l, r); ll ans = 0; if (p != root) { ans = cost[l] + cost[r] - 2 * cost[p] + U[p]; } else { ans = cost[l] + cost[r] - U[p]; } total_cost += ans * c; } cout << total_cost << endl; return 0; }