#include using namespace std; using ll = long long; using PII = std::pair; using PLL = std::pair; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) const int amax = 18; struct node { int depth; vector custom; vector ansestors; vector childrens; vector roads; }; vector nodes; void dfs(int s, int d) { nodes[s].depth = d; for (auto z : nodes[s].roads) { if (nodes[z].depth == -1) { dfs(z, d + 1); nodes[s].childrens.push_back(z); } else { nodes[s].ansestors[0] = z; } } } int cost_to_ansestors(int s, int n) { int m, c; c = 0; if (n == 0) return 0; else { m = n; while (m > 0 && m % 2 == 0) { c++; m /= 2; } return nodes[s].custom[c] + cost_to_ansestors(nodes[s].ansestors[c], n - pow(2, c)); } } int back_to_ansestors(int s, int n) { int m, c; c = 0; if (n == 0) return s; else { m = n; while (m > 0 && m % 2 == 0) { c++; m /= 2; } return back_to_ansestors(nodes[s].ansestors[c], n - pow(2, c)); } } int lca(int a, int b) { int dd, ok, ng, mid; dd = nodes[a].depth - nodes[b].depth; if (dd > 0) a = back_to_ansestors(a, dd); if (dd < 0) b = back_to_ansestors(b, abs(dd)); if (a == b) return a; if (a == 0 || b == 0) return 0; while (nodes[a].ansestors[0] != nodes[b].ansestors[0]) { for (int i = amax - 1; i > -1; i--) { if (nodes[a].ansestors[i] != nodes[b].ansestors[i]) { a = nodes[a].ansestors[i]; b = nodes[b].ansestors[i]; break; } } } return nodes[a].ansestors[0]; } int main() { #ifdef DEBUG cout << "DEBUG MODE" << endl; ifstream in("input.txt"); //for debug cin.rdbuf(in.rdbuf()); //for debug #endif int n, k, q, a, b, c, d, ans; cin >> n; vector cusint, ainit, cinit, rinit; rep(i, n) { nodes.push_back((node){-1, cusint, ainit, cinit, rinit}); } rep(i, n - 1) { cin >> a >> b; nodes[a].roads.push_back(b); nodes[b].roads.push_back(a); } rep(i, n) { rep(j, amax) { nodes[i].custom.push_back(0); nodes[i].ansestors.push_back(-1); } cin >> k; nodes[i].custom[0] = k; } dfs(0, 0); rep(j, amax - 1) { rep(i, n) { if (nodes[i].ansestors[j] != -1 && nodes[nodes[i].ansestors[j]].ansestors[j] != -1) { nodes[i].ansestors[j + 1] = nodes[nodes[i].ansestors[j]].ansestors[j]; nodes[i].custom[j + 1] = nodes[nodes[i].ansestors[j]].custom[j] + nodes[i].custom[j]; } } } ans = 0; cin >> q; rep(i, q) { cin >> a >> b >> c; d = lca(a, b); ans += c * nodes[d].custom[0]; ans += c * cost_to_ansestors(a, nodes[a].depth - nodes[d].depth); ans += c * cost_to_ansestors(b, nodes[b].depth - nodes[d].depth); } cout << ans << endl; // rep(i, n) // { // cout << nodes[i].depth << "\t"; // rep(j, amax) // { // cout << nodes[i].custom[j] << " "; // } // cout << "\t" << cost_to_ansestors(i, nodes[i].depth); // cout << endl; // } return 0; }