#include #include #include #include #define rep(i, n) for(int i = 0; i < (n); ++i) using ll = long long; constexpr int INF = 1073741823; using namespace std; /*----------------------------------------------------------------------------------*/ template struct sparsetable { vector> table; vector logtable; vector a; int n; sparsetable(const vector a, int siz) : n(siz), a(a) { logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector(logtable[n] + 1, 0)); } sparsetable(initializer_list init) { a = init[0]; n = init[1]; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector(logtable[n] + 1, 0)); } void init(const vector aa, int siz) { a = aa; n = siz; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector(logtable[n] + 1, 0)); } void init() { for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; } void build() { for (int k = 0; (1 << k) <= n; ++k) { for (int i = 0; i + (1 << k) <= n; ++i) { if (k) table[i][k] = (a[table[i][k - 1]] < a[table[i + (1 << (k - 1))][k - 1]] ? table[i][k - 1] : table[i + (1 << (k - 1))][k - 1]); else table[i][k] = i; } } } //[l, r) RMQ int query(int l, int r) { int k = logtable[r - l]; return (a[table[l][k]] < a[table[r - (1 << k)][k]] ? table[l][k] : table[r - (1 << k)][k]); } }; void eulertour(const int& now, const int& bef, int& cnt, const vector>>& graph, const int& d, vector& vs, vector& depth, vector& id) { depth.emplace_back(d); vs.emplace_back(now); id[now] = min(id[now], cnt); for (const auto& aa : graph[now]) { if (aa.first != bef) { ++cnt; eulertour(aa.first, now, cnt, graph, d + aa.second, vs, depth, id); ++cnt; depth.emplace_back(d); vs.emplace_back(now); } } } struct LCA { vector vs, depth, id, tmp = { 0 }; vector>> tree; sparsetable table{ tmp, 0 }; int n, root; LCA(vector>> tree, int n, int root) : tree(tree), n(n), root(root) { id.assign(n, INF); int cnt = 0, d = 0; eulertour(root, -1, cnt, tree, d, vs, depth, id); table.init(depth, depth.size()); table.build(); } int query(int l, int r) { if (id[l] > id[r])swap(l, r); return vs[table.query(id[l], id[r] + 1)]; } int depthq(int n) { return depth[id[n]]; } }; int main() { int n; scanf("%d", &n); vector>> g(n); rep(i, n - 1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); --a, --b; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } LCA lca(g, n, 0); int q; scanf("%d", &q); while (q--) { int s, t; scanf("%d%d", &s, &t); --s, --t; printf("%d\n", lca.depthq(s) + lca.depthq(t) - 2 * lca.depthq(lca.query(s, t))); } return 0; }