#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } // graph template // ref : https://ei1333.github.io/library/graph/graph-template.cpp template struct Edge{ int from,to; T w; int idx; Edge()=default; Edge(int from,int to,T w=1,int idx=-1):from(from),to(to),w(w),idx(idx){} operator int() const{return to;} }; template struct Graph{ vector>> g; int V,E; Graph()=default; Graph(int n):g(n),V(n),E(0){} size_t size(){ return g.size(); } void resize(int k){ g.resize(k); } inline const vector> &operator[](int k)const{ return (g.at(k)); } inline vector> &operator[](int k){ return (g.at(k)); } void add_directed_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E++); } void add_edge(int from,int to,T cost=1){ g[from].emplace_back(from,to,cost,E); g[to].emplace_back(to,from,cost,E++); } void read(int m,int pad=-1,bool weighted=false,bool directed=false){ for(int i=0;i>u>>v; u+=pad,v+=pad; T w=T(1); if(weighted) cin>>w; if(directed) add_directed_edge(u,v,w); else add_edge(u,v,w); } } }; struct HLD{ vector> g; // u以下の部分木->[in[u],out[u]) vector sz,in,out,head,rev,par,dep; HLD(vector> g): g(g),sz(g.size()),in(g.size()),out(g.size()),head(g.size()),rev(g.size()),par(g.size()){} void build(){ sz.assign(g.size(),0); in.assign(g.size(),0); out.assign(g.size(),0); head.assign(g.size(),0); rev.assign(g.size(),0); par.assign(g.size(),0); dep.assign(g.size(),0); dfs_sz(-1,0,0); int t=0; dfs_hld(-1,0,t); } int la(int v,int k){ while(true){ int u=head[v]; if(in[v]-k>=in[u]) return rev[in[v]-k]; k-=in[v]-in[u]+1; v=par[u]; } } int lca(int u,int v){ for(;;v=par[head[v]]){ /* heavyな辺から先に訪問している 訪問順が遅い方を上げていけばlcaを超えない*/ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) return u; } } int dis(int u,int v){ return dep[u]+dep[v]-2*dep[lca(u,v)]; } /* u-v のパスに関するクエリ ti: 元的な,ll付けるの忘れない q: パスの区間の求値関数,だいたいq(u,v)=seg.query(u,v) f: パスごとの結果をマージしていく関数 */ template E query(int u,int v,const E &ti,const Q &q,const F &f,bool edge=false){ E l=ti,r=ti; for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v),swap(l,r); if(head[u]==head[v]) break; l=f(q(in[head[v]],in[v]+1),l); } return f(f(q(in[u]+edge,in[v]+1),l),r); } template void add_path(int u,int v,const Q &q,bool edge=false){ for(;;v=par[head[v]]){ if(in[u]>in[v]) swap(u,v); if(head[u]==head[v]) break; q(in[head[v]],in[v]+1); } q(in[u]+edge,in[v]+1); } void dfs_sz(int pre,int now,int d){ dep[now]=d; par[now]=pre; sz[now]=1; if(g[now].size() and g[now][0]==pre) swap(g[now][0],g[now].back()); for(auto &to:g[now])if(to!=pre){ dfs_sz(now,to,d+1); sz[now]+=sz[to]; // 0がheavyな辺の先 if(sz[g[now][0]] vector> WarshallFloyd(vector> mat, T inf=1000000100){ int n=(int)mat.size(); for(int k=0;k>N>>K; Graph T(N); vector> tmp(N); rep(i,N-1){ int u,v;ll c;cin>>u>>v>>c;u--,v--; tmp[u].push_back(v); tmp[v].push_back(u); T.add_edge(u,v,c); } HLD LCA(tmp); LCA.build(); vector d_T(N,LINF); function dfs=[&](int pre,int cur){ for(auto &e:T[cur])if(e!=pre){ d_T[e]=d_T[cur]+e.w; dfs(cur,e); } }; d_T[0]=0; dfs(-1,0); vector> d_P(K,vector(N,LINF)); vector P(K); vector> X(K); rep(i,K){ int M;cin>>M>>P[i]; rep(j,M){ int x;cin>>x;x--; X[i].push_back(x); } } using PP=pair; rep(i,K){ priority_queue,greater> que; for(auto &st:X[i]){ d_P[i][st]=0; que.emplace(0,st); } while(!que.empty()){ auto [cur_d,cur]=que.top();que.pop(); if(d_P[i][cur]> MAT_K(K,vector(K,LINF)); rep(i,K)rep(j,K){ if(i==j) MAT_K[i][j]=P[i]; rep(k,N){ chmin(MAT_K[i][j],d_P[i][k]+d_P[j][k]+P[i]+P[j]); } } rep(k,K)rep(i,K)rep(j,K) chmin(MAT_K[i][j],MAT_K[i][k]+MAT_K[k][j]-P[k]); int Q;cin>>Q; while(Q--){ int u,v;cin>>u>>v;u--,v--; ll res=LINF; { int par=LCA.lca(u,v); chmin(res,d_T[u]+d_T[v]-2*d_T[par]); } rep(i,K)rep(j,K) chmin(res,d_P[i][u]+MAT_K[i][j]+d_P[j][v]); cout<