#include #include #include #include #include #include #include using namespace std; using ii = long long; using ll = long long; #define rep(i, N) for(ii i = 0; i < (N); i++) #define all(v) (v).begin(), (v).end() void chmin(auto& a, auto b) { a = (a < b ? a : b); } void chmax(auto& a, auto b) { a = (a > b ? a : b); } const ii INF = 1e9 + 10; const ll INFL = 4e18; // https://yukicoder.me/problems/no/898 #pragma once #include #include #include using namespace std; struct LCA { int lg; vector> par; vector dep; vector wei; LCA(const vector>>& g, int root = 0) { int n = g.size(); lg = bit_width((unsigned)n); par.assign(lg, vector(n, root)); dep.assign(n, 0); wei.assign(n, 0); auto dfs = [&](auto self, int v, int p) -> void { par[0][v] = p; for(auto [u, w] : g[v]) if(u != p) { dep[u] = dep[v] + 1; wei[u] = wei[v] + w; self(self, u, v); } }; dfs(dfs, root, root); for(int j = 1; j < lg; j++) for(int v = 0; v < n; v++) par[j][v] = par[j - 1][par[j - 1][v]]; } int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); int k = dep[u] - dep[v]; for(int j = 0; j < lg; j++) if(k >> j & 1) u = par[j][u]; if(u == v) return u; for(int j = lg - 1; j >= 0; j--) if(par[j][u] != par[j][v]) u = par[j][u], v = par[j][v]; return par[0][u]; } ll weight(int u, int v) { return wei[u] + wei[v] - 2 * wei[lca(u, v)]; } int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; void run() { int N; cin >> N; vector>> G(N); rep(i, N - 1) { int u, v, w; cin >> u >> v >> w; u--; v--; G[u].push_back({v, w}); G[v].push_back({u, w}); } LCA lca(G); int Q; cin >> Q; while(Q--) { int x, y, z; cin >> x >> y >> z; x--; y--; z--; vector st; st.push_back(lca.lca(x, y)); st.push_back(lca.lca(y, z)); st.push_back(lca.lca(z, x)); sort(all(st)); st.erase(unique(all(st)), st.end()); sort(all(st), [&](ii l, ii r) { return lca.dep[l] < lca.dep[r]; }); ii top = st[0]; ll ans = 0; ans += lca.weight(top, x); ans += lca.weight(top, y); ans += lca.weight(top, z); if(lca.lca(x, y) != top) ans -= lca.weight(top, lca.lca(x, y)); if(lca.lca(y, z) != top) ans -= lca.weight(top, lca.lca(y, z)); if(lca.lca(z, x) != top) ans -= lca.weight(top, lca.lca(z, x)); cout << ans << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while(T--) run(); }