#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000000000000 vector ind; vector D; template struct segtree{ //元データx[i]はv[n+i] //v[i]の親はv[i/2],子はv[i*2]とv[i*2+1] vector v; int n; const T init_value = 0; segtree(vector &x){ n=1; while(true){ if(n>=x.size())break; n*=2; } v.resize(2*n,init_value); for(int i=0;i=0;i--){ v[i]=func(v[i*2],v[i*2+1]); } } void update(int x,T val){ x+=n; v[x]=val; while(true){ x=(x)/2; v[x]=func(v[x*2],v[x*2+1]); if(x<=0)break; } } //区間[l,r)におけるクエリ処理 T query(int l,int r){ T res = init_value; if(l>=r)return res; l+=n;r+=n; while(true){ if(l%2==1){ res=func(v[l],res); l++; } if(r%2==1){ res=func(v[r-1],res); r--; } if(l>=r)break; l/=2;r/=2; } return res; } T func(T a,T b){ return a+b; } void show(){ int n = 1; for(int i=1;i depth;//depth[i] 頂点iの深さ vector> parents;//parents[i][j] 頂点iから2^j個上の親 int max_j = 30; lca(int n,vector> &E){ depth.assign(E.size(),-1); parents.assign(E.size(),vector(max_j,-1)); stack s; s.push(n); depth[n] = 0; while(s.size()!=0){ int k = s.top(); s.pop(); for(int i=0;i=0;i--){ if(parents[u][i]!=parents[v][i]){ u = parents[u][i]; v = parents[v][i]; } } return parents[u][0]; } int get_distance(int u,int v){ return depth[u]+depth[v]-2*depth[query(u,v)]; } }; void dfs(vector>> &E,int now,int parent){ for(int i=0;i &seg,lca &L,vector &I,int x,int y){ int p = L.query(x,y); int xx = I[x]; int yy = I[y]; int pp = I[p]; return seg.query(0,xx+1)+seg.query(0,yy+1)-2*seg.query(0,pp+1); } int main(){ int N; cin>>N; vector> E(N,vector()); vector>> Ew(N,vector>()); for(int i=0;i>a>>b; long long w; cin>>w; E[a].push_back(b); E[b].push_back(a); Ew[a].emplace_back(b,w); Ew[b].emplace_back(a,w); } lca L(0,E); ind.push_back(0); D.push_back(0); dfs(Ew,0,-1); vector I(N,-1); for(int i=0;i seg(D); int Q; cin>>Q; for(int i=0;i>x>>y>>z; long long A = get_dis(seg,L,I,x,y); long long B = get_dis(seg,L,I,y,z); long long C = get_dis(seg,L,I,z,x); //cout<