#include #define rep(i,n) for(int i = 0; i < (n); ++i) #define drep(i,n) for(int i = (n)-1; i >= 0; --i) #define srep(i,s,t) for (int i = s; i < t; ++i) using namespace std; typedef long long int ll; typedef pair P; #define yn {puts("YES");}else{puts("NO");} struct edge{ int to, cost; }; #define MAX_N 200005 #define MAX_LOG_N 25 vector pre_G[MAX_N]; vector G[MAX_N]; int par_[MAX_N]; int parent[MAX_LOG_N][MAX_N]; int flag_netsukigi[MAX_N]; int depth[MAX_N]; int root; void make_netsukigi(int r){ root = r; queue que; que.push(r); flag_netsukigi[r] = 1; par_[r] = -1; depth[r] = 0; while(que.size() > 0){ int x = que.front(); que.pop(); flag_netsukigi[x] = 1; rep(i,pre_G[x].size()){ if(flag_netsukigi[pre_G[x][i].to] == 0){ par_[pre_G[x][i].to] = x; depth[pre_G[x][i].to] = depth[x] + 1; G[x].push_back(pre_G[x][i]); que.push(pre_G[x][i].to); } } } } void 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].to != p) dfs(G[v][i].to, v, d + 1); } } void init(int V){ dfs(root, -1, 0); for(int k = 0; k + 1 < MAX_LOG_N; 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_N; k++){ if((depth[v] - depth[u]) >> k & 1){ v = parent[k][v]; } } if(u == v)return u; for(int k = MAX_LOG_N - 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[MAX_N]; void init_dist(int r){ dist[r] = 0; queue que; que.push(r); while(que.size() > 0){ int x = que.front(); que.pop(); for(int i = 0; i < G[x].size(); i++){ int y = G[x][i].to; dist[y] = dist[x] + G[x][i].cost; que.push(y); } } } int calcLength(int x, int y){ int w = lca(x, y); int m = dist[x] - dist[w] + dist[y] - dist[w]; return m; } int main() { int n; cin >> n; int a[n-1], b[n-1]; rep(i,n-1){ cin >> a[i] >> b[i]; // a[i]--; b[i]--; edge e; e.to = b[i]; e.cost = 1; pre_G[a[i]].push_back(e); e.to = a[i]; pre_G[b[i]].push_back(e); } make_netsukigi(0); init(n); init_dist(0); ll u[n] = {}; rep(i,n) cin >> u[i]; ll plus[n] = {}, minus[n] = {}; int q; cin >> q; rep(_,q){ int s, t, c; cin >> s >> t >> c; // s--; t--; int l = lca(s,t); plus[s] += c; plus[t] += c; minus[l] += c; } int sons[n] = {}; queue que; rep(i,n){ sons[i] = G[i].size(); if(sons[i] == 0) que.push(i); } ll ans = 0; ll dp[n] = {}; while(que.size()){ int x = que.front(); que.pop(); dp[x] += plus[x]; dp[x] -= minus[x]; ans += dp[x] * u[x]; dp[x] -= minus[x]; if(x == 0) continue; int y = par_[x]; dp[y] += dp[x]; sons[y]--; if(sons[y] == 0) que.push(y); } cout << ans << endl; return 0; }