#include using namespace std; #define ALL(x) x.begin(),x.end() #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> graph; struct DoublingLowestCommonAncestor{ const int LOG; vector dep; const graph &g; //table[i][j]は点jの2^i個上の親情報 vector> table; DoublingLowestCommonAncestor(const graph &g):g(g),dep(g.size()),LOG(32-__builtin_clz(g.size())){ table.assign(LOG,vector(g.size(),-1)); } void dfs(int idx,int par,int d){ //1個上の親の記録 table[0][idx]=par; dep[idx]=d; for(auto &to:g[idx]){ if(to!=par) dfs(to,idx,d+1); } } //根としたい点をroot void build(int root){ dfs(root,-1,0); for(int k=0;k+1dep[v]として進める if(dep[u]>dep[v]) swap(u,v); //深さをそろえる for(int i=LOG-1;i>=0;i--){ if(((dep[v]-dep[u])>>i)&1) v=table[i][v]; } if(u==v) return u; for(int i=LOG-1;i>=0;i--){ if(table[i][u]!=table[i][v]){ u=table[i][u]; v=table[i][v]; } } return table[0][u]; } //呼び出すたびO(logn) int dis(int u,int v){ int p=query(u,v); return dep[u]+dep[v]-2*dep[p]; } //いるか?これ int operator[](const int &k) const{ return dep[k]; } //頂点xのk個上の親を求める。無ければ-1,未verify int parent(int x,int k){ int ret=x; int bit=0; for(int i=LOG-1;i>=0 and ret>=0;i--){ if((k>>i)&1) ret=table[i][ret]; } return ret; } }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; vector> g(n); vector>> gw(n); rep(i,n-1){ int u,v;ll w;cin>>u>>v>>w; g[u].push_back(v); g[v].push_back(u); gw[u].push_back(make_pair(v,w)); gw[v].push_back(make_pair(u,w)); } DoublingLowestCommonAncestor lca(g); lca.build(0); vector dis(n,0); function dfs=[&](int pre,int now){ for(auto &e:gw[now])if(e.first!=pre){ dis[e.first]=dis[now]+e.second; dfs(now,e.first); } }; dfs(-1,0); int q;cin>>q; while(q--){ int x,y,z;cin>>x>>y>>z; int pxy=lca.query(x,y); int pyz=lca.query(y,z); int pzx=lca.query(z,x); int p=lca.query(pxy,z); ll a=dis[x]-dis[p]; ll b=dis[y]-dis[p]; ll c=dis[z]-dis[p]; ll ab=dis[pxy]-dis[p]; ll bc=dis[pyz]-dis[p]; ll ca=dis[pzx]-dis[p]; cout<