#define _USE_MATH_DEFINES #include using namespace std; ///////////////////////////////////////////////////////////////////////// // LCA ///////////////////////////////////////////////////////////////////////// class LowestCommonAncestor { public: LowestCommonAncestor(); LowestCommonAncestor(const vector>& g, int r); LowestCommonAncestor(const vector g[], int r, int siz); ~LowestCommonAncestor(); void build(const vector>& g, int r); void build(const vector g[], int r, int siz); inline int get(int u, int v) const; inline int getParent(int cur, int u) const; inline int getDepth(int cur) const; inline void debugTree () const; private: void initialize(); void dfs(int cur, int par, int d); static constexpr int MAX_SIZE = 30; vector> graph; vector> parent; vector depth; int bit_; int root; }; LowestCommonAncestor::LowestCommonAncestor() {}; LowestCommonAncestor::LowestCommonAncestor(const vector>& g, int r = -1) : graph(g), root(r) { if (root == -1) root = 0; initialize(); } LowestCommonAncestor::LowestCommonAncestor(const vector g[], int r = -1, int siz = -1) : root(r) { assert(siz > 0); if (root == -1) root = 0; graph.resize(siz); for (int i = 0; i < siz; i++) for (auto& j : g[i]) graph[i].push_back(j); initialize(); } LowestCommonAncestor::~LowestCommonAncestor() {}; void LowestCommonAncestor::build(const vector>& g, int r = -1) { root = r; graph = g; if (root == -1) root = 0; initialize(); } void LowestCommonAncestor::build(const vector g[], int r = -1, int siz = -1) { assert(siz > 0); root = r; graph.resize(siz); for (int i = 0; i < siz; i++) for (auto& j : g[i]) graph[i].push_back(j); initialize(); } inline int LowestCommonAncestor::get(int u, int v) const { assert(u >= 0 && u < (int) graph.size()); assert(v >= 0 && v < (int) graph.size()); if (depth[u] > depth[v]) swap(u, v); for (int i = 0; i < bit_; ++i) if (((depth[v] - depth[u]) >> i) & 1) v = parent[v][i]; if (u == v) return u; for (int i = bit_ - 1; i >= 0; --i) if (parent[u][i] != parent[v][i]) u = parent[u][i], v = parent[v][i]; return parent[u][0]; } inline int LowestCommonAncestor::getParent(int cur, int u = 0) const { if ((int) parent[cur].size() <= u) return -1; //assert(cur >= 0 && cur < (int) parent.size()); //assert(u >= 0 && (int) parent[cur].size() > u); return parent[cur][u]; } inline int LowestCommonAncestor::getDepth(int cur) const { assert(cur >= 0 && cur < (int) depth.size()); return depth[cur]; } void LowestCommonAncestor::initialize() { bit_ = 1; while ((1 << bit_) < (int) graph.size()) ++bit_; parent = vector>((int) graph.size(), vector(bit_)); depth.assign((int) graph.size(), -1); dfs(root, -1, 0); for (int i = 0; i < bit_ - 1; ++i) { for (int v = 0; v < (int) graph.size(); ++v) { if (depth[v] == -1) continue; if (parent[v][i] < 0) parent[v][i + 1] = -1; else parent[v][i + 1] = parent[parent[v][i]][i]; } } } void LowestCommonAncestor::dfs(int cur, int par, int d) { parent[cur][0] = par; depth[cur] = d; for (auto& child : graph[cur]) if (child != par) dfs(child, cur, d + 1); } void LowestCommonAncestor::debugTree () const { cerr << "size " << parent.size() << endl; for (int i = 0; i < (int) parent.size(); i++) { cerr << "the parent of " << i << " -> " << parent[i][0] << endl; } cerr << endl; for (int i = 0; i < (int) graph.size(); i++) { cerr << "the neighbor of " << i << " -> "; for (const int& j : graph[i]) cerr << j << " "; cerr << endl; } } using LCA = LowestCommonAncestor; ///////////////////////////////////////////////////////////////////////// // END LCA ///////////////////////////////////////////////////////////////////////// vector dist; vector>> g; vector> gg; void dfs (int cur, int par) { for (auto child : g[cur]) if (child.first != par) { dist[child.first] = dist[cur] + child.second; dfs(child.first, cur); } } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; g = vector>>(n); gg = vector>(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; int c; cin >> c; g[u].emplace_back(v, c); g[v].emplace_back(u, c); gg[u].push_back(v); gg[v].push_back(u); } dist = vector(n); dfs(0, -1); LCA lca(gg); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; u--; v--; cout << dist[u] - dist[lca.get(u, v)] * 2 + dist[v] << '\n'; } return 0; }