#include #include #include #include #include #include #include #include #include #include #include #define fir first #define sec second #define sz(s) (s).size() #define pb push_back #define get(n) scanf("%d",&n); #define gets(s) string s;cin >> (s); #define prfi(n) printf("%d", &n); #define prfd(n) printf("%lf", &n); #define All(s) (s).begin(), (s).end() #define rep(i,j) for(int (i)=0;(i)<(j);(i)++) #define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++) #define drep(i,j) for(int (i)=(j);(i)>=0;(i)--) #define Ford(i,j,k) for(int (i)=(j);i>=(k);i--) #define fore(c,v) for(auto (c): (v)) #define lp for(int __=0;__; using pll = std::pair; using vi = std::vector ; using vvi = std::vector ; using vll = std::vector; using vvll = std::vector; using vd = std::vector ; using vvd = std::vector ; using qi = std::queue ; using vpii = std::vector >; using vpll = std::vector; using namespace std; const int Mod = (1e9) + 7; const int INF = 1e9 + 19; const ll INFL = 1e18 + 19; const int dx[] = {-1, 0, 0, 1}; const int dy[] = {0, -1, 1, 0}; const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}; const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1}; const double EPS = 1e-10; //_____________________________________Templates_________________________________________// template inline void chmin(T1 &a, T2 b){if(a > b) a = b;} template inline void chmax(T1 &a, T2 b){if(a < b) a = b;} template inline void pri(T a){cout << a << endl;} template using vec = vector; template using min_priority_queue = priority_queue, greater>; //mainly use for dynamic prog template void update(T1 &a, T2 b){ a += b; if(a > Mod) a %= Mod; } inline void IN(void){ return; } template void IN(First& first, Rest&... rest){ cin >> first; IN(rest...); return; } inline void OUT(void){ cout << "\n"; return; } template void OUT(First first, Rest... rest){ cout << first << " "; OUT(rest...); return; } bool pairsort(pll pl, pll pr){ if(pl.first == pr.first)return pl.second > pr.second; return pl.first < pr.first; } int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;} vector make_bit(int a){vector res; for(int i=31;i>=0;i--)if(a&(1< a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);} int LCM(int a, int b){return a*b/GCD(a,b);} int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;} int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}} ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;} ll GetDiviserCount(ll N)//約数の個数 { ll res = 1; For(i,2,sqrt(N)+1) { ll cnt = 0; while(N%i == 0) { cnt++; N /= i; } res *= (cnt + 1); if(N == 1)break; } if(N != 1)res *= 2; return res; } vll GetDivisor(ll N)//約数列挙 { vll res; for(ll i = 1;i*i <= N;i++) { if(N%i == 0) { res.pb(i); if(i*i != N)res.pb(N/i); } } sort(All(res)); return res; } struct mint { ll x; // typedef long long ll; mint(ll x=0):x((x%Mod+Mod)%Mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= Mod) x -= Mod; return *this; } mint& operator-=(const mint a) { if ((x += Mod-a.x) >= Mod) x -= Mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= Mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(Mod-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& a); }; ostream& operator<<(ostream& os, const mint& a) { os << a.x; return os; } struct combination { vector fact, ifact; combination(int n):fact(n+1),ifact(n+1) { assert(n < Mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i; } mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return fact[n]*ifact[k]*ifact[n-k]; } }; template struct Matrix { using mat = Matrix; vector> m_dat; int m_h; int m_w; Matrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector(w)) {} vector &operator[] (int idx) { return m_dat[idx]; } mat Multiple(mat &a) { mat C(m_h, a.m_w); for(int i=0;i 0) { if(x&1)B = B.Multiple(A); A = A.Multiple(A); x = x >> 1; } return B; } friend ostream& operator<<(ostream &os, const mat &A); }; template ostream& operator<<(ostream &os, Matrix& A) { for(int i=0;i using mat = Matrix; //_____________________ following sorce code_________________________// const int max_n = 3 * (1e5) + 1; const int max_m = 83 * (1e5) + 1; int n,m,k; ll N; int h,w; string S; int a,b,c; vi v; int ans; double x,y,z; vector G[1010101]; struct Edge { int to; long long int x; Edge() {} Edge(int to, long long int x) : to(to), x(x){} }; struct LCA { int n; int rmq_n; int m; int root; vector vs;// 行きがけ順に頂点を並べた vector depth;// 頂点ごとのふかさ vector dist;// 最短路 vector dat;// それぞれの頂点がはじめに出現するインデックス vector G[101010]; vector rmq_data;// rmq 用の配列 LCA(int n) : n(n), vs(2*n-1),depth(2*n-1), dat(n), dist(n) {} void AddEdge(int v, int u, long long int x) { G[v].push_back({u,x}); G[u].push_back({v,x}); } void init(int ro) { root = ro; int k = 0; dfs(root, -1, 0, k, 0); rmq_init(); } void dfs(int curr, int last,int d, int &k,long long int dis) { dat[curr] = k; vs[k] = curr; depth[k++] = d; dist[curr] = dis; for(auto e: G[curr]) { if(e.to == last)continue; dfs(e.to, curr, d+1, k, dis + e.x); vs[k] = curr; depth[k++] = d; } } Edge lca(int a, int b) { Edge e = find(min(dat[a], dat[b]), max(dat[a], dat[b]) + 1); return e; } int GetDepth(int a, int b) { return depth[dat[a]] + depth[dat[b]] - 2*depth[dat[lca(a,b).to]]; } long long int GetDist(int a, int b) { return dist[a] + dist[b] - dist[lca(a,b).to]*2; } // rmq methods void rmq_init() { m = n*2 - 1; rmq_n = 1; while(rmq_n < m)rmq_n *= 2; rmq_data.resize(rmq_n*2-1,Edge(-1,10101010101)); for(int i=0;i 0) { idx = (idx-1)/2; rmq_data[idx] = change(rmq_data[idx*2+1], rmq_data[idx*2+2]); } } Edge change(Edge a, Edge b) { if(a.x > b.x)return b; else return a; } Edge query(int a,int b, int c, int l, int r) { Edge Unit(-1, 101010110); if(b <= l or r <= a)return Unit; if(a <= l and r <= b)return rmq_data[c]; return change(query(a,b,c*2+1,l,(r+l)/2), query(a,b,c*2+2,(r+l)/2,r)); } Edge find(int a,int b) { return query(a,b,0,0,rmq_n); } }; signed main (int argc, char* argv[]) { cin.tie(0); ios::sync_with_stdio(false); IN(n); LCA lc(n); rep(i,n-1) { ll c; IN(a,b,c); lc.AddEdge(a,b,c); } lc.init(0); int q; IN(q); ll ans = 0; rep(i,q) { IN(a,b,c); int ancestor = lc.lca(a,b).to; ans = lc.GetDist(a,b) + lc.GetDist(b,c) + lc.GetDist(c,a); ans /= 2; pri(ans); } //for(auto c : ans){cout << c << endl;} //cout << fixed << setprecision(15) << ans << endl; return 0; }