#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; template< typename G=vector> > struct HeavyLightDecomposition { G &g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G &g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for(auto &to : g[idx]) { if(to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int ×) { in[idx] = times++; rev[in[idx]] = idx; for(auto &to : g[idx]) { if(to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while(1) { int u = head[v]; if(in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) { T l = ti, r = ti; for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v), swap(l, r); if(head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); } template< typename Q > void add(int u, int v, const Q &q, bool edge = false) { for(;; v = par[head[v]]) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; vector> G; vector> g; ll d[100010]; void dfs(int x, int p){ for(auto q:g[x]){ int y=q.first; ll w=q.second; if(y!=p){ d[y]=d[x]+w; dfs(y, x); } } } int main() { int n; cin>>n; g.resize(n); for(int i=0; i>u>>v>>w; u--; v--; G[u].push_back(v); G[v].push_back(u); g[u].push_back({v, w}); g[v].push_back({u, w}); } HeavyLightDecomposition<> hld(G); hld.build(); dfs(0, -1); int Q; cin>>Q; for(int i=0; i>x>>y>>z; x--; y--; z--; ll ans=0; int p=hld.lca(x, y); ans+=d[x]+d[y]-2*d[p]; p=hld.lca(y, z); ans+=d[y]+d[z]-2*d[p]; p=hld.lca(z, x); ans+=d[z]+d[x]-2*d[p]; ans/=2; cout<