#include using namespace std; //#define int long long //TEMPLATE START---------------8<---------------8<---------------8<---------------8<---------------// typedef long long ll; typedef long double ld; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vl; typedef vector vst; typedef vector vb; typedef vector vld; typedef vector vpii; typedef vector vpll; typedef vector > vvi; const int INF = (0x7FFFFFFFL); const ll INFF = (0x7FFFFFFFFFFFFFFFL); const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const int MOD = 1e9 + 7; const int MODD = 998244353; const string alphabet = "abcdefghijklmnopqrstuvwxyz"; const double PI = acos(-1.0); const double EPS = 1e-9; const string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; int dx[9] = { 1, 0, -1, 0, 1, -1, -1, 1, 0 }; int dy[9] = { 0, 1, 0, -1, -1, -1, 1, 1, 0 }; #define ln '\n' #define scnaf scanf #define sacnf scanf #define sancf scanf #define SS(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template void MACRO_VAR_Scan(T& t){cin >> t;}template void MACRO_VAR_Scan(First& first, Rest&...rest){cin >> first;MACRO_VAR_Scan(rest...);} #define SV(type,c,n) vector c(n);for(auto& i:c)cin >> i; #define SVV(type,c,n,m) vector> c(n,vector(m));for(auto& r:c)for(auto& i:r)cin >> i; templateostream &operator<<(ostream &o,const pair&j){o<<"{"<ostream &operator<<(ostream &o,const map&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;} templateostream &operator<<(ostream &o,const set&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;} templateostream &operator<<(ostream &o,const multiset&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;} templateostream &operator<<(ostream &o,const vector&j){o<<"{";for(int i=0;i<(int)j.size();++i)o<<(i>0?", ":"")< int print(Head&& head){cout << head;print();return 0;} template int print(Head&& head,Tail&&... tail){cout<(tail)...);return 0;} inline int debug(void){cerr << endl; return 0;} template int debug(Head&& head){cerr << head;debug();return 0;} template int debug(Head&& head,Tail&&... tail){cerr<(tail)...);return 0;} template void PA(T &a){int ASIZE=sizeof(a)/sizeof(a[0]);for(int ii=0;ii void PV(T &v){int VSIZE=v.size();for(int ii=0;ii void sankou(bool x,A a,B b){cout<<((x)?(a):(b))<=ll(b);--i) #define RREP(...) _overload3(__VA_ARGS__,RREPI,_RREP,)(__VA_ARGS__) #define EACH(e,v) for(auto& e : v) #define PERM(v) sort((v).begin(),(v).end());for(bool c##p=1;c##p;c##p=next_permutation((v).begin(),(v).end())) #define ADD(a,b) a=(a+ll(b))%MOD #define MUL(a,b) a=(a*ll(b))%MOD inline ll MOP(ll x,ll n,ll m=MOD){ll r=1;while(n>0){if(n&1)(r*=x)%=m;(x*=x)%=m;n>>=1;}return r;} inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}inline ll POW(ll a,ll b){ll c=1ll;do{if(b&1)c*=1ll*a;a*=1ll*a;}while(b>>=1);return c;} template inline bool between(T x,A a,B b) {return ((a<=x)&&(x inline T sqr(T x){return x*x;} template inline bool chmax(A &a,const B &b){if(a inline bool chmin(A &a,const B &b){if(a>b){a=b;return 1;}return 0;} #define tmax(x,y,z) max((x),max((y),(z))) #define tmin(x,y,z) min((x),min((y),(z))) #define PB push_back #define MP make_pair #define MT make_tuple #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define SORT(v) sort((v).begin(),(v).end()) #define RSORT(v) sort((v).rbegin(),(v).rend()) #define EXIST(s,e) (find((s).begin(),(s).end(),(e))!=(s).end()) #define EXISTST(s,c) (((s).find(c))!=string::npos) #define POSL(x,val) (lower_bound(x.begin(),x.end(),val)-x.begin()) #define POSU(x,val) (upper_bound(x.begin(),x.end(),val)-x.begin()) #define GEQ(x,val) (int)(x).size() - POSL((x),(val)) #define GREATER(x,val) (int)(x).size() - POSU((x),(val)) #define LEQ(x,val) POSU((x),(val)) #define LESS(x,val) POSL((x),(val)) #define SZV(a) int((a).size()) #define SZA(a) sizeof(a)/sizeof(a[0]) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MEMINF(a) memset(a,0x3f,sizeof(a)) #define FILL(a,b) memset(a,b,sizeof(a)) #define UNIQUE(v) sort((v).begin(),(v).end());(v).erase(unique((v).begin(),(v).end()),(v).end()) struct abracadabra{ abracadabra(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); cerr << fixed << setprecision(5); }; } ABRACADABRA; //TEMPLATE END---------------8<---------------8<---------------8<---------------8<---------------// template< typename G > struct DoublingLowestCommonAncestor { const int LOG; vector< int > dep; const G &g; vector< vector< int > > table; DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) { table.assign(LOG, vector< int >(g.size(), -1)); } void dfs(int idx, int par, int d) { table[0][idx] = par; dep[idx] = d; for(auto &to : g[idx]) { if(to != par) dfs(to, idx, d + 1); } } void build() { dfs(0, -1, 0); for(int k = 0; k + 1 < LOG; k++) { for(int i = 0; i < table[k].size(); i++) { if(table[k][i] == -1) table[k + 1][i] = -1; else table[k + 1][i] = table[k][table[k][i]]; } } } int query(int u, int 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]; } }; vector dist; vector> g; vector>> graph; void init(int cur, ll d = 0) { if (dist[cur] != -1) return; dist[cur] = d; EACH(nxt_p, graph[cur]) { int nxt, wei; tie(nxt, wei) = nxt_p; init(nxt, d + wei); } } signed main() { SS(int, N); g.assign(N, vector()); graph.assign(N, vector>()); dist.assign(N, -1); const int root = 0; REP(i, N - 1) { SS(int, U, V, W); g[U].emplace_back(V); g[V].emplace_back(U); graph[U].emplace_back(make_pair(V, W)); graph[V].emplace_back(make_pair(U, W)); } init(root); DoublingLowestCommonAncestor>> lca(g); lca.build(); SS(int, Q); while (Q--) { SS(int, X, Y, Z); int XY = lca.query(X, Y); int YZ = lca.query(Y, Z); int ZX = lca.query(Z, X); if (XY == YZ) { if (YZ == ZX) { if (XY == X) { cout << dist[Y] + dist[Z] - dist[X] * 2 << endl; } else if (XY == Y) { cout << dist[Z] + dist[X] - dist[Y] * 2 << endl; } else if (XY == Z) { cout << dist[X] + dist[Y] - dist[Z] * 2 << endl; } continue; } cout << dist[X] + dist[Z] - dist[ZX] * 2 + (lca.query(ZX, Y) == root ? dist[ZX] + dist[Y] : (dist[ZX] > dist[Y] ? dist[ZX] + dist[Y] - dist[lca.query(ZX, Y)] : 0)) << endl; } else if (YZ == ZX) { cout << dist[Y] + dist[X] - dist[XY] * 2 + (lca.query(XY, Z) == root ? dist[XY] + dist[Z] : (dist[XY] > dist[Z] ? dist[XY] + dist[Z] - dist[lca.query(XY, Z)] : 0)) << endl; } else if (ZX == XY) { cout << dist[Z] + dist[Y] - dist[YZ] * 2 + (lca.query(YZ, X) == root ? dist[YZ] + dist[X] : (dist[YZ] > dist[X] ? dist[YZ] + dist[X] - dist[lca.query(YZ, X)] : 0)) << endl; } } }