#include #include template struct Edge { int src, dst; Cost cost; Edge(int src = -1, int dst = -1, Cost cost = 1) : src(src), dst(dst), cost(cost){}; bool operator<(const Edge& e) const { return this->cost < e.cost; } bool operator>(const Edge& e) const { return this->cost > e.cost; } }; template struct Graph { std::vector>> graph; Graph(int n = 0) : graph(n) {} void span(bool direct, int src, int dst, Cost cost = 1) { graph[src].emplace_back(src, dst, cost); if (!direct) graph[dst].emplace_back(dst, src, cost); } std::vector>& operator[](int v) { return graph[v]; } std::vector> operator[](int v) const { return graph[v]; } int size() const { return graph.size(); } }; template struct LevelAncestor { Graph tree; std::vector> par; std::vector depth; std::vector cdepth; int kmax; void dfs(int v, int p = -1, int d = 0, Cost c = 0) { par[v][0] = p; depth[v] = d; cdepth[v] = c; for (const auto& e : tree[v]) { if (e.dst == p) continue; dfs(e.dst, v, d + 1, c + e.cost); } } LevelAncestor(const Graph& tree, int root) : tree(tree), par(tree.size()), depth(tree.size(), -1), cdepth(tree.size()) { kmax = 0; while ((1 << kmax) < (int)tree.size()) ++kmax; for (auto& v : par) v.resize(kmax + 1); dfs(root); for (int k = 1; k <= kmax; ++k) { for (int v = 0; v < tree.size(); ++v) { int p = par[v][k - 1]; par[v][k] = (p == -1 ? -1 : par[p][k - 1]); } } } int climb(int v, int d) const { for (int k = kmax; k >= 0 && v != -1; --k) { if ((1 << k) > d) continue; v = par[v][k]; d -= (1 << k); } return v; } int lca(int u, int v) const { if (depth[u] < depth[v]) std::swap(u, v); if (depth[u] > depth[v]) { u = climb(u, depth[u] - depth[v]); } if (u == v) return u; for (int k = kmax; k >= 0; --k) { if (par[u][k] != par[v][k]) { u = par[u][k]; v = par[v][k]; } } return par[u][0]; } int dist(int u, int v) const { int p = lca(u, v); return depth[u] + depth[v] - depth[p] * 2; } Cost cdist(int u, int v) const { int p = lca(u, v); return cdepth[u] + cdepth[v] - cdepth[p] * 2; } }; using lint = long long; void solve() { int n; std::cin >> n; Graph graph(n); for (int i = 0; i < n - 1; ++i) { int u, v; lint d; std::cin >> u >> v >> d; graph.span(false, u, v, d); } LevelAncestor la(graph, 0); int q; std::cin >> q; while (q--) { std::vector vs(3); for (auto& v : vs) std::cin >> v; lint c = 0; for (int i = 0; i < 3; ++i) { c += la.cdist(vs[i], vs[(i + 1) % 3]); } std::cout << c / 2 << std::endl; } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }