#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(ll (i)=0;(i)<(n);(i)++) #define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++) #define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i) #define ll long long #define ull unsigned long long #define all(hoge) (hoge).begin(),(hoge).end() #define en '\n' typedef pair P; const long long INF = 1LL << 60; const long long MOD = 1e9 + 7; typedef vector Array; typedef vector Matrix; const int loose = 0; const int tight = 1; template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //グラフ関連 struct Edge {//グラフ ll to, cap, rev; Edge(ll _to, ll _cap, ll _rev) { to = _to; cap = _cap; rev = _rev; } }; typedef vector Edges; typedef vector Graph; void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) { G[from].push_back(Edge(to, cap, (ll)G[to].size())); if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1)); } class lca { public: const int n = 0; const int log2_n = 0; vector> parent; vector depth; lca() {} lca(const Graph& g, int root) : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector(n)), depth(n) { dfs(g, root, -1, 0); for (int k = 0; k + 1 < log2_n; k++) { for (int v = 0; v < (int)g.size(); v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } //深さを求める+1個上の親を保存 void dfs(const Graph& g, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (auto& e : g[v]) { if (e.to != p) dfs(g, e.to, v, d + 1); } } //LCA(最小共通祖先)をえる int get(int u, int v) { //頂点の深さをあわせるために、深さが浅い法を遡らせる if (depth[u] > depth[v]) std::swap(u, v); for (int k = 0; k < log2_n; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } //降順で親が一致しない場合は遡る if (u == v) return u; for (int k = log2_n - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } //最短経路 int d(int u, int v) { return depth[u] + depth[v] - 2 * depth[get(u, v)]; } }; void dfs(const Graph& g, Array& depth, int v, int p, ll d) { depth[v] = d; for (auto& e : g[v]) { if (e.to != p) dfs(g, depth, e.to, v, d + e.cap); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n; cin >> n; Graph g(n); REP(i, n-1) { ll x,y,c; cin >> x>>y>>c; add_edge(g, x, y, c, true, c); } lca lc(g, 0); Array d(n); dfs(g, d, 0, -1, 0); ll q; cin >> q; while (q--) { ll ans = INF; int v[3]; REP(i, 3)cin >> v[i]; REP(i, 3) { int m = lc.get(v[i], v[(i+1)%3]); ll dd = d[v[i]] + d[v[(i+1)%3]] - 2 * d[m]; dd += d[v[(i+2)%3]] + d[m] - 2 * d[lc.get(v[(i+2)%3], m)]; chmin(ans, dd); } cout << ans << en; } return 0; }