#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a, b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define show(x) cout <<#x<<" = "<<(x)<P; const int MAX_N = 100005; vector G[MAX_N]; vector ord; vector vec; vector val; int depth[MAX_N]; int id[MAX_N]; int id2[MAX_N]; bool flag[MAX_N]; //インデックスは0始まり //最小値を求めるプログラム(RMQ) const int N = 1 << 18; //10^5程度 //セグメント木を持つグローバル配列 int n_; int dat[2*N-1]; int idx[2*N-1]; //初期化 //n_はx以上の最小の2のべき乗 void init(int x) { //簡単のため、要素数を2のべき乗に n_=1; while(n_0){ k = (k-1)/2; if(dat[2*k+1] < dat[2*k+2]){ dat[k] = dat[2*k+1]; idx[k] = idx[2*k+1]; }else{ dat[k] = dat[2*k+2]; idx[k] = idx[2*k+2]; } } } P query(int a,int b,int k=0,int l=0,int r=n_) { if(r <= a || b <= l){ return P(INF,-1); } if(a <= l && r <= b){ return P(dat[k],idx[k]); }else{ P vl = query(a,b,2*k+1,l,(l+r)/2); P vr = query(a,b,2*k+2,(l+r)/2,r); return min(vl,vr); } } void dfs(int u,int k) { id[u] = (int)ord.size(); id2[u] = (int)vec.size(); ord.pb(u); vec.pb(val[u]); flag[u] = true; depth[u] = k; rep(i,G[u].size()){ if(!flag[G[u][i]]){ dfs(G[u][i],k+1); ord.pb(u); } } vec.pb(-val[u]); } template class segtree { private: int n,sz; vector node, lazy; public: segtree(vector v) { sz = (int)v.size(); n = 1; while(n < sz){ n *= 2; } node.resize(2*n-1); lazy.resize(2*n-1, 0); rep(i,sz){ node[i+n-1] = v[i]; } for(int i=n-2; i>=0; i--){ node[i] = node[i*2+1] + node[i*2+2]; } } void eval(int k, int l, int r) { if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) { lazy[2*k+1] += lazy[k] / 2; lazy[2*k+2] += lazy[k] / 2; } lazy[k] = 0; } } void range(int a, int b, V x, int k=0, int l=0, int r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a){ return; } if(a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } else { range(a, b, x, 2*k+1, l, (l+r)/2); range(a, b, x, 2*k+2, (l+r)/2, r); node[k] = node[2*k+1] + node[2*k+2]; } } V query(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a){ return 0; } if(a <= l && r <= b){ return node[k]; } V vl = query(a, b, 2*k+1, l, (l+r)/2); V vr = query(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } void print() { rep(i,sz){ cout << query(i,i+1) << " "; } cout << endl; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; rep(i,n-1){ int a,b; cin >> a >> b; G[a].pb(b); G[b].pb(a); } val.resize(n); rep(i,n){ cin >> val[i]; } dfs(0,0); init(ord.size()); rep(i,ord.size()){ update(i,depth[ord[i]]); } segtree sg(vec); int q; cin >> q; ll ans = 0; rep(i,q){ int a,b,c; cin >> a >> b >> c; int lca = ord[query(min(id[a],id[b]),max(id[a],id[b])+1).se]; int sm = sg.query(min(id2[a],id2[lca]),max(id2[a],id2[lca])+1) + sg.query(min(id2[b],id2[lca]),max(id2[b],id2[lca])+1); sm -= val[lca]; ans += (ll)sm*c; } cout << ans << endl; return 0; }