//include //------------------------------------------ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";} #define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}} using LL = long long; //------------------------------------------ //------------------------------------------ template struct Edge { int from, to; T cost; Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} explicit operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnWeightedGraph = vector>; template using DistMatrix = vector>; struct GraphAdapter { template static UnWeightedGraph to_unweighted_graph(const WeightedGraph &origin) { int V = origin.size(); UnWeightedGraph graph(V); for (int i = 0; i < V; i++) for (auto &e: origin[i]) graph[i].push_back((int) e); return graph; } static WeightedGraph to_weighted_graph(const UnWeightedGraph &origin) { int V = origin.size(); WeightedGraph graph(V); for (int i = 0; i < V; i++) for (auto to: origin[i]) graph[i].push_back({i, to, 1}); return graph; } }; struct Doubling { const long long LOG; const int N; vector> nexted; Doubling(int N, long long log = 60) : N(N), LOG(log) { nexted.assign(LOG + 1, vector(N + 1, -1)); } inline void set_init_next(const int v, const int x) { nexted[0][v] = x; } void build() { for (int k = 0; k < LOG; k++) { for (int v = 0; v < N; v++) { if (nexted[k][v] == -1) nexted[k + 1][v] = -1; else nexted[k + 1][v] = nexted[k][nexted[k][v]]; } } } inline int query(int v, long long p) { for (long long i = LOG; i >= 0; i--) { if (v < 0) return -1; if (p & (1LL << i)) { v = nexted[i][v]; } } return v; } }; template class LowestCommonAncestor { private: const long long LOG; const int N; const WeightedGraph &graph; vector depth; vector dist; vector> nexted; public: LowestCommonAncestor(const WeightedGraph &graph, const long long LOG = 60) : graph(graph), LOG(LOG), N(graph.size()), depth(N, -1), dist(N, numeric_limits::max()) { nexted.assign(LOG + 1, vector(N, -1)); } void dfs(int v, int p, int d, long long sum) { depth[v] = d; dist[v] = sum; nexted[0][v] = p; for (auto e: graph[v]) { int to = e.to; long long cost = e.cost; if (to != p) { dfs(to, v, d + 1, sum + cost); } } } void build(int s) { dfs(s, -1, 0, 0); for (int k = 0; k < LOG; k++) { for (int v = 0; v < N; v++) { if (nexted[k][v] == -1) nexted[k + 1][v] = -1; else nexted[k + 1][v] = nexted[k][nexted[k][v]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (long long i = LOG - 1; i >= 0; i--) { if ((depth[v] - depth[u]) & (1LL << i)) { v = nexted[i][v]; } } if (u == v)return u; for (long long i = LOG - 1; i >= 0; i--) { if (nexted[i][u] != nexted[i][v]) { u = nexted[i][u]; v = nexted[i][v]; } } return nexted[0][u]; } T get_distance(int u, int v) { T sum = dist[u] + dist[v] - 2 * dist[lca(u, v)]; return sum; } }; int main() { int N; cin >> N; WeightedGraph graph(N); for (int i = 0; i < N - 1; i++) { int s, t, w; cin >> s >> t >> w; graph[s].push_back({s, t, w}); graph[t].push_back({t, s, w}); } LowestCommonAncestor LCA(graph); LCA.build(0); int Q; cin >> Q; while (Q--) { vector xyz(3); for (int i = 0; i < 3; i++) cin >> xyz[i]; sort(xyz.begin(), xyz.end()); long long ans = LONG_LONG_MAX; do { long long sum = LCA.get_distance(xyz[0], xyz[1]); auto s = LCA.lca(xyz[0], xyz[1]); sum += LCA.get_distance(s, xyz[2]); ans = min(ans, sum); } while (next_permutation(xyz.begin(), xyz.end())); cout << ans << endl; } return 0; }