#include #define rep(i, a, n) for(int i = a; i < n; i++) #define int long long using namespace std; typedef pair P; const int mod = 1000000007; const int INF = 1e18; struct LowestCommonAncestor{ const int MAX_LOG_V = 50; vector > G, parent; int root = 0, V; vector depth; LowestCommonAncestor(int _V){ V = _V; G.resize(V); parent.resize(MAX_LOG_V, vector(V)); depth.resize(V); } void add_edge(int u, int v){ G[u].push_back(v); G[v].push_back(u); } void dfs(int v, int p, int d){ parent[0][v] = p; depth[v] = d; for(int i = 0; i < G[v].size(); i++){ if(G[v][i] != p) dfs(G[v][i], v, d + 1); } } void build(){ dfs(root, -1, 0); for(int k = 0; k + 1 < MAX_LOG_V; k++){ for(int v = 0; v < V; v++){ if(parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } int query(int u, int v){ if(depth[u] > depth[v]) swap(u, v); for(int k = 0; k < MAX_LOG_V; k++){ if((depth[v] - depth[u]) >> k & 1){ v = parent[k][v]; } } if(u == v) return u; for(int k = MAX_LOG_V - 1; k >= 0; k--){ if(parent[k][u] != parent[k][v]){ u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; struct BIT{ int N; vector dat; BIT() {} BIT(int n) { N = n; dat.resize(N + 1); } // update k th element (0-index) void add(int k, int x){ k++; while(k <= N){ dat[k] += x; k += k&-k; } } // sum [0, k) (0-index) int sum(int k){ int s = 0; while(k > 0){ s += dat[k]; k -= k&-k; } return s; } // sum [a, b) (0-index) int query(int a, int b){ return sum(b) - sum(a); } }; class Euler_Tour{ public: vector > g; //begin[v],end[v]はそれぞれvがオイラーツアー上で最初と最後に現れるインデックス //[begin[v], end[v])がvを根とする部分木 (半開区間に注意) vector euler_tour, begin, end, dist; Euler_Tour(int n) : /* g(n),*/ begin(n), end(n){}; int k = 0, root = 0; void dfs(int curr, int par){ begin[curr] = k; euler_tour.push_back(curr); k++; for(auto next : g[curr]){ if(next == par) continue; dfs(next, curr); euler_tour.push_back(curr); k++; } end[curr] = k; } }; struct edge{ int v, w; }; vector G[100010]; map cst; int sum[100010]; int depth[100010]; int dfs(int v, int p, int dep){ depth[v] = dep; if(G[v].size() == 1) return 0; for(auto i : G[v]){ if(i.v == p) continue; sum[v] += dfs(i.v, v, dep + 1) + i.w; } return sum[v]; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; LowestCommonAncestor lca(n); Euler_Tour et(n); et.g.resize(n); rep(i, 0, n - 1){ int u, v, w; cin >> u >> v >> w; G[u].push_back({v, w}); G[v].push_back({u, w}); lca.add_edge(u, v); et.g[u].push_back(v); et.g[v].push_back(u); cst[{u, v}] = w; cst[{v, u}] = w; } dfs(0, -1, 0); et.dfs(0, -1); BIT bt(2 * n); lca.build(); rep(i, 0, 2 * n - 2){ int u = et.euler_tour[i]; int v = et.euler_tour[i + 1]; if(depth[u] < depth[v]) bt.add(i, cst[{u, v}]); else bt.add(i, -cst[{u, v}]); } int q; cin >> q; while(q--){ vector p(3); cin >> p[0] >> p[1] >> p[2]; int ans = INF; sort(p.begin(), p.end()); do{ int u1 = lca.query(p[0], p[1]); int u2 = lca.query(p[1], p[2]); int tmp = bt.query(et.begin[u1], et.begin[p[0]]) + bt.query(et.begin[u1], et.begin[p[1]]) + bt.query(et.begin[u2], et.begin[p[2]]) + abs(bt.query(et.begin[u1], et.begin[u2])); ans = min(ans, tmp); }while(next_permutation(p.begin(), p.end())); cout << ans << endl; } }