#include // c #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include using namespace std; typedef long long ll;typedef unsigned long long ull;typedef long double ld; #define ALL(c) c.begin(),c.end() #define IN(l,v,r) (l<=v && v < r) template void UNIQUE(T& v){v.erase(unique(ALL(v)),v.end());} //debug #define DUMP(x) cerr << #x <<" = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" struct range{ struct Iter{ int v,step; Iter& operator++(){v+=step;return *this;} bool operator!=(Iter& itr){return vitr.v;} int& operator*(){return v;} }; Iter i, n; rrange(int i, int n,int step):i({i-1,step}), n({n-1,step}){} rrange(int i, int n):rrange(i,n,1){} rrange(int n) :rrange(0,n){} Iter& begin(){return n;} Iter& end(){return i;} }; //input template istream& operator >> (istream& is,pair& p){return is>>p.first>>p.second;} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t) >> get<1>(t);} template istream& operator >> (istream& is,tuple& t){return is >>get<0>(t)>>get<1>(t)>>get<2>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);} template istream& operator >> (istream& is,vector& as){for(int i:range(as.size()))is >>as[i];return is;} //output template ostream& operator << (ostream& os, const set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< ostream& operator << (ostream& os, const pair& p){return os< ostream& operator << (ostream& os, const map& m){bool isF=true;for(auto& p:m){if(!isF)os< ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const vector& as){for(int i:range(as.size())){if(i!=0)os<<" "; os< ostream& operator << (ostream& os, const vector>& as){for(int i:range(as.size())){if(i!=0)os< inline T INF(){assert(false);}; template<> inline int INF(){return 1<<28;}; template<> inline ll INF(){return 1LL<<58;}; template<> inline double INF(){return 1e16;}; template<> inline long double INF(){return 1e16;}; template inline T EPS(){assert(false);}; template<> inline int EPS(){return 1;}; template<> inline ll EPS(){return 1LL;}; template<> inline double EPS(){return 1e-8;}; template<> inline long double EPS(){return 1e-8;}; // min{2^r | n < 2^r} template T upper_pow2(T n){ T res=1;while(res T msb(T n){ int d=62;while((1LL<n)d--;return d;} template T pmod(T v,U M){return (v%M+M)%M;} class Main{ public: typedef vector> Graph; //O(Q * logN) class DoublingLCA{ Graph& g;int r; vector > parent; vector > ds; vector depth; public: DoublingLCA(Graph& g,int r,vector us):g(g),r(r),parent(msb(g.size())+1,vector(g.size())),ds(msb(g.size())+1,vector(g.size())),depth(vector(g.size())){ dfs(-1,r,0); ds[0] = us; for(int l:range(1,parent.size()))for(int s:range(parent[l].size())){ parent[l][s] = (parent[l-1][s]==-1)?-1:parent[l-1][parent[l-1][s]]; ds[l][s] = (parent[l-1][s]==-1)?ds[l-1][s]:ds[l-1][parent[l-1][s]] + ds[l-1][s]; } } void dfs(int p,int s,int d){ parent[0][s]=p;depth[s]=d; for(int t:g[s])if(t!=p)dfs(s,t,d+1); } int lca(int u,int v){ if(depth[u]>depth[v])swap(u,v); for(int l:range(parent.size()))if((depth[v]-depth[u])&(1<=0;l--)if(parent[l][u]!=parent[l][v]){ u=parent[l][u]; v=parent[l][v]; } return parent[0][u]; } ll getD(int u,int v){ ll res = 0; if(depth[u]>depth[v])swap(u,v); for(int l:range(parent.size()))if((depth[v]-depth[u])&(1<=0;l--)if(parent[l][u]!=parent[l][v]){ res += ds[l][u]; u=parent[l][u]; res += ds[l][v]; v=parent[l][v]; } res += ds[0][u]; res += ds[0][v]; res += ds[0][parent[0][u]]; return res; } }; void run(){ int N;cin >> N; vector> es(N); for(int i:range(N-1)){ int u,v;cin >> u >> v; es[u].push_back(v); es[v].push_back(u); } vector us(N);cin >> us; DoublingLCA lca(es, 0, us); int M;cin >> M; ll res = 0; for(int q:range(M)){ int a,b; ll c;cin >> a >> b >> c; res += lca.getD(a,b)*c; } cout << res << endl; } }; int main(){ cout <