#include using namespace std; #define rep(i,n) for(int i = 0 ; i < (n) ; i++) #define int long long // intを64bit intにしてます!!! template struct SegmentTree{ int n_; vector seg; // [1,N] SegmentTree(int N){ n_ = 1; while(n_ < N ) n_ *= 2; seg.resize(2*n_,0); //要設定 } void add(int i,int j,int v){ i += n_-1; seg[i] = v; i /= 2; while(i){ seg[i] = seg[i*2] + seg[i*2+1]; //要設定 i /= 2; } } T get(int l,int r,int k,int a,int b){ if( b < l || r < a ) return 0; //要設定 if( l <= a && b <= r ){ return seg[k]; } int m = (a+b)/2; return get(l,r,k*2,a,m) + get(l,r,k*2+1,m+1,b); //要設定 } inline T get(int l,int r){ return get(l,r,1,1,n_); } }; class Tree{ public: //[0,n) int n,logn,root; vector> child; vector> parent; vector> edges; vector depth; Tree(int n_,vector> es,int root) : root(root){ edges = es; n = n_; logn = 0; while(n_){ ++logn; n_ /= 2; } parent.resize(logn,vector(n,-1)); depth.resize(n,-1); child.resize(n); vector> g(n); for( auto e : es ){ g[e.first].push_back(e.second); g[e.second].push_back(e.first); } dfs(g); gen_lca(); verify(); } bool verify(){ for(int i = 0 ; i < n ; i++) assert( depth[i] != -1 ); } int lca(int x,int y){ if( depth[x] < depth[y] )swap(x,y); int d = depth[x] - depth[y]; for(int i = 0 ; i < logn ; i++) if( d >> i & 1 ) x = parent[i][x]; if( x == y ) return x; for(int i = logn-1 ; i >= 0 ; i--){ if( parent[i][x] != parent[i][y] ){ x = parent[i][x]; y = parent[i][y]; } } return parent[0][x]; } int distance(int x,int y){ return depth[x] + depth[y] - 2 * depth[lca(x,y)]; } private: int gen_lca(){ for(int i = 1 ; i < logn ; i++){ for(int j = 0 ; j < n ; j++) if( parent[i-1][j] != -1 ) parent[i][j] = parent[i-1][parent[i-1][j]]; } } int dfs(const vector> &g){ stack< array > S; S.push(array{root,-1,0}); while( S.size() ){ int x = S.top()[0]; int p = S.top()[1]; int d = S.top()[2]; S.pop(); parent[0][x] = p; depth[x] = d; for( auto e : g[x] ){ if( e != p ){ S.push(array{e,x,d+1}); child[x].push_back(e); } } } } }; template class HeavyLightDecomp{ public: Tree tr; vector< pair > where; // (id,pos) vector< vector > pathSeq; vector seg; HeavyLightDecomp(const Tree &tr) : tr(tr){ // init where.resize(tr.n,{-1,-1}); vector subtree(tr.n); vector> sortedIdx; for(int i = 0 ; i < tr.n ; i++) sortedIdx.push_back({tr.depth[i],i}); sort(sortedIdx.begin(),sortedIdx.end()); // calc sizes of each subtree for(int I = tr.n-1 ; I >= 0 ; I--){ int i = sortedIdx[I].second; subtree[i] = 1; for( auto e : tr.child[i] ) subtree[i] += subtree[e]; } // do heavyLightDecomp Part1 for(int I = 0 ; I < tr.n ; I++){ int i = sortedIdx[I].second; if( where[i].first == -1 ){ where[i].first = pathSeq.size(); pathSeq.push_back(vector()); } where[i].second = pathSeq[where[i].first].size(); pathSeq[where[i].first].push_back(i); for( auto e : tr.child[i] ){ if( 2*subtree[e] > subtree[i] ){ where[e].first = where[i].first; } } } // Set segtrees to each heavy-path. for(int i = 0 ; i < pathSeq.size() ; i++){ int n_ = 1; while( n_ < pathSeq[i].size() ) n_ *= 2; seg.push_back(SegmentTree(n_)); } } //加算点の重複に気をつけて void addToVertex(int a,int b,int x){ int p = tr.lca(a,b); add(a,p,x,1); //要設定 add(b,p,x,0); //要設定 } int getToVertex(int a,int b){ int p = tr.lca(a,b); return get(a,p,1) + get(b,p,0); //要設定 } private: inline void add(int c,int p,int x,int isEdgeQuery){ int id1 = where[c].first; int id2 = where[p].first; int l = where[p].second + 1; int r = where[c].second + 1; if( id1 == id2 ){ if( l+isEdgeQuery <= r ) seg[id1].add(l+isEdgeQuery,r,x); //要設定 }else{ seg[id1].add(1,r,x); //要設定 add(tr.parent[0][pathSeq[id1][0]],p,x,isEdgeQuery); } } inline int get(int c,int p,int isEdgeQuery){ int id1 = where[c].first; int id2 = where[p].first; int l = where[p].second + 1; int r = where[c].second + 1; int ans = 0; if( id1 == id2 ){ ans += seg[id1].get(l+isEdgeQuery,r); //要設定 }else{ ans += seg[id1].get(1,r); //要設定 ans += get(tr.parent[0][pathSeq[id1][0]],p,isEdgeQuery); } return ans; } }; signed main(){ int n; cin >> n; vector< pair > es; for(int i = 0 ; i < n - 1 ; i++){ int a,b; cin >> a >> b; es.push_back({a,b}); } Tree tree(n,es,0); HeavyLightDecomp> hl(tree); for(int i = 0 ; i < n ; i++){ int w; cin >> w; hl.addToVertex(i,i,w); } int q; cin >> q; int ans = 0; for(int i = 0 ; i < q ; i++){ int a,b,c; cin >> a >> b >> c; ans += c * hl.getToVertex(a,b); } cout << ans << endl; }