#include #ifndef DUMP #define DUMP(...) void(0) #endif using namespace std; struct graph { struct edge { int src, dst; int64_t cost; int operator-(int v) const { return src ^ dst ^ v; } }; int n, m; vector edges; vector>> adj; graph(int _n = 0) : n(_n), m(0), adj(n) {} int add(const edge& e, bool directed = false) { edges.push_back(e); adj[e.src].emplace_back(m, e.dst); if (not directed) adj[e.dst].emplace_back(m, e.src); return m++; } }; struct dfs_forest : graph { using T = decltype(edge::cost); vector root, pv, pe, sz, dep, min_dep, last, ord, in, out; vector dist; int trials; dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) { for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out}) p->assign(n, -1); } int add(const edge& e) { return graph::add(e); } void dfs(int v) { sz[v] = 1, min_dep[v] = dep[v], last[v] = trials; in[v] = size(ord), ord.push_back(v); for (auto [id, u] : adj[v]) { if (id == pe[v]) continue; if (last[u] == trials) { min_dep[v] = min(min_dep[v], dep[u]); continue; } root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1; dist[u] = dist[v] + edges[id].cost; dfs(u); sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]); } out[v] = size(ord); } void build(int r, bool clear_ord = true) { root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{}; if (clear_ord) ord.clear(); dfs(r); ++trials; } void build() { fill(begin(root), end(root), -1); for (int v = 0; v < n; ++v) if (root[v] == -1) build(v, v == 0); } int farther(int id) const { int u = edges[id].src, v = edges[id].dst; return dep[u] < dep[v] ? v : u; } bool spans(int id) const { return id == pe[farther(id)]; } bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; } }; struct hld_forest : dfs_forest { vector head; hld_forest(int _n = 0) : dfs_forest(_n), head(n) {} void dfs_hld(int v) { in[v] = size(ord), ord.push_back(v); sort(begin(adj[v]), end(adj[v]), [&](auto a, auto b) { int au = a.second, bu = b.second; return (a.first == pe[au]) * sz[au] > (b.first == pe[bu]) * sz[bu]; }); for (auto [id, u] : adj[v]) { if (id == pe[v] or not spans(id)) continue; head[u] = u == adj[v][0].second ? head[v] : u; dfs_hld(u); } out[v] = size(ord); } void build_hld(int r, bool clear_ord = true) { build(r, clear_ord); ord.erase(end(ord) - sz[r], end(ord)); head[r] = r; dfs_hld(r); } void build_hld() { fill(begin(root), end(root), -1); for (int v = 0; v < n; ++v) if (root[v] == -1) build_hld(v, v == 0); } int lca(int u, int v) const { assert(root[u] == root[v]); while (true) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; v = pv[head[v]]; } } int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } T distance(int u, int v) const { return dist[u] + dist[v] - 2 * dist[lca(u, v)]; } int la(int v, int d) const { assert(0 <= d), assert(d <= dep[v]); while (dep[head[v]] > d) v = pv[head[v]]; return ord[in[head[v]] + (d - dep[head[v]])]; } int next(int src, int dst) const { assert(root[src] == root[dst]), assert(src != dst); if (not anc(src, dst)) return pv[src]; return la(dst, dep[src] + 1); } int next(int src, int dst, int k) const { assert(root[src] == root[dst]), assert(k >= 0); int v = lca(src, dst); if (k <= dep[src] - dep[v]) return la(src, dep[src] - k); k -= dep[src] - dep[v]; assert(k <= dep[dst] - dep[v]); return la(dst, dep[v] + k); } vector> ascend(int src, int dst) const { vector> res; while (head[src] != head[dst]) { res.emplace_back(in[src], in[head[src]]); src = pv[head[src]]; } if (src != dst) res.emplace_back(in[src], in[dst] + 1); return res; } vector> descend(int src, int dst) const { if (src == dst) return {}; if (head[src] == head[dst]) return {{in[src] + 1, in[dst]}}; auto res = descend(src, pv[head[dst]]); res.emplace_back(in[head[dst]], in[dst]); return res; } template void run(int src, int dst, F f, bool vertex = true) const { assert(root[src] == root[dst]); int v = lca(src, dst); for (auto [a, b] : ascend(src, v)) f(a + 1, b); if (vertex) f(in[v], in[v] + 1); for (auto [a, b] : descend(v, dst)) f(a, b + 1); } }; constexpr int inf = 0x3f3f3f3f; template struct segtree { int n; vector t; segtree(int _n = 0) : n(_n), t(2 * n) {} T& operator[](int i) { return t[n + i]; } void build() { for (int i = n; i-- > 1;) t[i] = t[2 * i] * t[2 * i + 1]; } T fold(int l, int r) const { T a{}, b{}; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) a = a * t[l++]; if (r & 1) b = t[--r] * b; } return a * b; } void set(int i, const T& a) { t[i += n] = a; while (i >>= 1) t[i] = t[2 * i] * t[2 * i + 1]; } }; struct node { int v; node(int _v = inf) : v(_v) {} operator int() const { return v; } friend node operator*(const node& a, const node& b) { return b.v < a.v ? b : a; } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n; cin >> n; hld_forest g(n); for (int _ = n - 1; _--;) { int u, v, w; cin >> u >> v >> w; --u, --v; g.add({u, v, w}); } g.build_hld(); segtree seg(n); vector> ch(n); vector sz(n); for (int v = 0; v < n; ++v) { sz[v] = size(g.adj[v]) - (v >= 1); ch[v] = sz[v]; for (int i = 0; i < sz[v]; ++i) { auto [id, u] = g.adj[v][i]; ch[v][i] = g.edges[id].cost; } ch[v].build(); for (int i = 0; i < sz[v]; ++i) { auto [id, u] = g.adj[v][i]; seg[g.in[u]] = min(ch[v].fold(0, i), ch[v].fold(i + 1, sz[v])); } } seg.build(); auto fold = [&](int u, int v) { int res = inf; g.run( u, v, [&](int l, int r) { if (l > r) swap(l, r); res = min(res, seg.fold(l, r)); }, false); return res; }; int q; cin >> q; while (q--) { int u, v; cin >> u >> v; --u, --v; if (g.in[u] > g.in[v]) swap(u, v); int a = g.lca(u, v); int64_t res = g.distance(u, v); int mn = inf; if (u == a) { mn = min(mn, fold(u, v)); mn = min(mn, ch[v].fold(0, sz[v])); } else { int au = g.next(a, u); int av = g.next(a, v); mn = min(mn, fold(u, au)); mn = min(mn, fold(v, av)); mn = min(mn, ch[u].fold(0, sz[u])); mn = min(mn, ch[v].fold(0, sz[v])); assert(g.in[au] < g.in[av]); int x = partition_point( begin(g.adj[a]), begin(g.adj[a]) + sz[a], [&](auto idu) { return g.in[idu.second] < g.in[au]; }) - begin(g.adj[a]); int y = partition_point( begin(g.adj[a]), begin(g.adj[a]) + sz[a], [&](auto idu) { return g.in[idu.second] < g.in[av]; }) - begin(g.adj[a]); mn = min(mn, ch[a].fold(0, x)); mn = min(mn, ch[a].fold(x + 1, y)); mn = min(mn, ch[a].fold(y + 1, sz[a])); } if (a) mn = min(mn, g.edges[g.pe[a]].cost); if (mn == inf) res = -1; else res += 2 * mn; cout << res << '\n'; } }