# include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include using namespace std; using LL = long long; using ULL = unsigned long long; constexpr int INF = 2147483647; constexpr int HINF = INF / 2; constexpr double DINF = 100000000000000000.0; constexpr double HDINF = 50000000000000000.0; constexpr long long LINF = 9223372036854775807; constexpr long long HLINF = 4500000000000000000; const double PI = acos(-1); int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }; template T_char TL(T_char cX) { return tolower(cX); }; template T_char TU(T_char cX) { return toupper(cX); }; # define ALL(x) (x).begin(),(x).end() # define UNIQ(c) (c).erase(unique(ALL((c))),(c).end()) # define LOWER(s) transform(ALL((s)),(s).begin(),TL) # define UPPER(s) transform(ALL((s)),(s).begin(),TU) # define mp make_pair # define eb emplace_back # define FOR(i,a,b) for(LL i=(a);i<(b);i++) # define RFOR(i,a,b) for(LL i=(a);i>=(b);i--) # define REP(i,n) FOR(i,0,n) # define INIT std::ios::sync_with_stdio(false);std::cin.tie(0) int n, m, root; vector g[101010]; int depth[101010]; int par[101010][30]; LL u[101010]; LL cost[101010]; //木の深さを求める void dfs(int v, int p, int d) { par[v][0] = p; depth[v] = d; if (p != -1) { cost[v] = cost[p] + u[v]; } else { cost[v] = u[v]; } for (int i = 0; i < g[v].size(); i++) { if (g[v][i] == p)continue; dfs(g[v][i], v, d + 1); } } //par[v][i]:=頂点vから2^i回親をたどった頂点(無かったら-1) //vの親→par[v][0],vの親の親par[v][1] //par[v][i+1]=par[par[v][i]]よりpar[~][i]が計算できればpar[~][i+1]も求まる void fill_table() { for (int i = 0; i < 19; i++) { for (int j = 0; j < n; j++) { if (par[j][i] == -1)par[j][i + 1] = -1; else par[j][i + 1] = par[par[j][i]][i]; } } } //頂点u,vのLCAを求める int lca(int u, int v) { if (depth[u] > depth[v])swap(u, v); //深さをそろえるための処理 for (int i = 19; i >= 0; i--) { if (((depth[v] - depth[u]) >> i) & 1) { v = par[v][i]; } } if (u == v)return u; //ダブリング for (int i = 19; i >= 0; i--) { if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } LL ans = 0; int main() { cin >> n; REP(i, n - 1) { int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); root = a; } REP(i, n)cin >> u[i]; dfs(root, -1, 0); fill_table(); /*cout << root << endl; REP(i, n)cout << cost[i] << endl; system("pause"); */ cin >> m; REP(i, m) { int a, b, c; cin >> a >> b >> c; int lp = lca(a, b); ans += (cost[a] + cost[b] - cost[lp] * 2 + u[lp])*c; } cout << ans << endl; //system("pause"); return 0; }