#include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 100010; const int MAX_LOG_V = 30; vector G[MAX_V]; const int root = 0; int parent[MAX_LOG_V][MAX_V]; int depth[MAX_V]; void lca_dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int i = 0; i < G[v].size(); i++) { if (G[v][i] != p) lca_dfs(G[v][i], v, d + 1); } } void init(int V) { lca_dfs(root, -1, 0); for (int k = 0; k + 1 < MAX_LOG_V; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAX_LOG_V; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int N, M; ll U[100010]; ll sum[100010]; void dfs(int n, int p, ll s) { sum[n] = s + U[n]; for (int c : G[n]) { if (c != p) dfs(c, n, s + U[n]); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } init(N); for (int i = 0; i < N; i++) { cin >> U[i]; } dfs(0, -1, 0); ll ans = 0; cin >> M; for (int i = 0; i < M; i++) { int A, B, C; cin >> A >> B >> C; int cp = lca(A, B); ans += C * (sum[A] + sum[B] - sum[cp] * 2 + U[cp]); } cout << ans << endl; }