// #define DEBUGGING #include using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template using V = vector; template using VV = V>; using ll = int64_t; using ull = uint64_t; using PLL = pair; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } #ifdef DEBUGGING // #include "../debug/debug.cpp" #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif template T make_v(T init) { return init; } template auto make_v(T init, size_t s, Tail... tail) { #define rec make_v(init, tail...) return V(s, rec); #undef rec } template class Lca { const ll nopt; ll N; ll root; V depth; VV edge; VV parents; void dfs(ll now, ll pre, ll d) { parents[now][0] = pre; depth[now] = d; for(ll next : edge[now]) { if(next != pre) { dfs(next, now, d + 1); } } } public: Lca(ll N, ll root, const vector> &e) : nopt(-1), N(N), root(root), edge(e), parents(N, V(Size)) { depth.resize((size_t)N); dfs(root, nopt, 0); for(ll i = 1; i < Size; i++) { for(ll node = 0; node < N; node++) { if(parents[node][i - 1] == nopt) { parents[node][i] = nopt; } else { parents[node][i] = parents[parents[node][i - 1]][i - 1]; } } } } Lca(ll n, const vector> &e) : Lca(n, 0, e) { } ll get_depth(ll node) { return depth[node]; } ll get_parents(ll node, ll relative_depth) { ll ret = node; for(ll i = 0; (1 << i) <= relative_depth && ret != -1; i++) { if(relative_depth & (1 << i)) { ret = parents[ret][i]; } } return ret; } ll get_lca(ll n1, ll n2) { ll d = min(depth[n1], depth[n2]); ll ok = 0, ng = d + 1; ll ret = 0; while(abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; ll p1 = get_parents(n1, depth[n1] - mid); ll p2 = get_parents(n2, depth[n2] - mid); if(p1 == p2) { ok = mid; ret = p1; } else { ng = mid; } } return ret; } }; void calc_wd(ll cur, ll pre, const VV &edges, V &weight, ll cur_weight) { weight[cur] = cur_weight; for(auto &&edge : edges[cur]) { ll nxt, cost; tie(nxt, cost) = edge; if(nxt == pre) continue; calc_wd(nxt, cur, edges, weight, cur_weight + cost); } } int main() { ll N; cin >> N; VV wedges(N); VV edges(N); { auto add_edge = [&](ll u, ll v, ll w) { wedges[u].emplace_back(v, w); edges[u].push_back(v); }; for(ll i = 1; i < N; i++) { ll u, v, w; cin >> u >> v >> w; add_edge(u, v, w); add_edge(v, u, w); } } V weight(N); calc_wd(0, -1, wedges, weight, 0); Lca<30> lca(N, 0, edges); ll Q; cin >> Q; ll xyz[3]; while(Q--) { DEBUG(Q); for(ll i = 0; i < 3; i++) cin >> xyz[i]; sort(xyz, xyz + 3); ll ans = 5e15; do { ll cost = 0; ll cur_lca = xyz[0]; for(ll i = 1; i <= 2; i++) { ll nxt_lca = lca.get_lca(cur_lca, xyz[i]); DEBUG(make_tuple(cur_lca, nxt_lca, xyz[i], weight[cur_lca], weight[xyz[i]], weight[nxt_lca])); cost += weight[cur_lca] + weight[xyz[i]] - 2 * weight[nxt_lca]; cur_lca = nxt_lca; } chmin(ans, cost); } while(next_permutation(xyz, xyz + 3)); cout << ans << endl; } return 0; }