#include #include using namespace std; //Disjoint Sparse Table #include #include template struct DST{ functioncalcfn; int n; vector >dat; DST(const vector&v={}, functioncalcfn_=[](T a,T b){return a(n)); for(int j=i;jn)r=n; r--; if(l==r)return dat[0][l]; int k=31-__builtin_clz(l^r); return calcfn(dat[k][l],dat[k][r]); } }; int N; vector >G[1<<17]; int depth[1<<17]; long weighth[1<<17]; int id[1<<17]; vectoreuler; void dfs(int u,int p,int d,long wei) { depth[u]=d; weighth[u]=wei; id[u]=euler.size(); euler.push_back(u); for(pairq:G[u]) { if(q.first==p)continue; dfs(q.first,u,d+1,wei+q.second); euler.push_back(u); } } main() { cin>>N; for(int i=1;i>u>>v>>w; G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } dfs(0,-1,0,0); DSTP(euler,[](int x,int y){return depth[x]>Q; for(;Q--;) { int x,y,z;cin>>x>>y>>z; int xy=P.query(min(id[x],id[y]),max(id[x],id[y])+1); int yz=P.query(min(id[y],id[z]),max(id[y],id[z])+1); int zx=P.query(min(id[z],id[x]),max(id[z],id[x])+1); cout<