#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #include using namespace std; const int INF = 1000000000; const int LOG = 18; struct lowest_common_ancestor{ vector d; vector> p; lowest_common_ancestor(){ } lowest_common_ancestor(vector &P, vector> &C){ int N = P.size(); d = vector(N, 0); queue Q; Q.push(0); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (int w : C[v]){ d[w] = d[v] + 1; Q.push(w); } } p = vector>(LOG, vector(N, -1)); for (int i = 0; i < N; i++){ p[0][i] = P[i]; } for (int i = 1; i < LOG; i++){ for (int j = 0; j < N; j++){ if (p[i - 1][j] != -1){ p[i][j] = p[i - 1][p[i - 1][j]]; } } } } int query(int u, int v){ if (d[u] > d[v]){ swap(u, v); } for (int k = 0; k < LOG; k++){ if ((d[v] - d[u]) >> k & 1){ v = p[k][v]; } } if (u == v){ return u; } for (int k = LOG - 1; k >= 0; k--){ if (p[k][u] != p[k][v]){ u = p[k][u]; v = p[k][v]; } } return p[0][u]; } }; template struct binary_indexed_tree{ int N; vector BIT; binary_indexed_tree(){ } binary_indexed_tree(int n){ N = 1; while (N < n){ N *= 2; } BIT = vector(N + 1, 0); } void add(int i){ i++; while (i <= N){ BIT[i]++; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } T query(int L, int R){ return sum(R) - sum(L); } }; template struct heavy_light_decomposition{ lowest_common_ancestor LCA; vector p; vector sz, in, next; int t; binary_indexed_tree BIT; void dfs1(vector> &c, int v = 0){ sz[v] = 1; for (int &w : c[v]){ dfs1(c, w); sz[v] += sz[w]; if (sz[w] > sz[c[v][0]]){ swap(w, c[v][0]); } } } void dfs2(vector> &c, int v = 0){ in[v] = t; t++; for (int w : c[v]){ if (w == c[v][0]){ next[w] = next[v]; } else { next[w] = w; } dfs2(c, w); } } heavy_light_decomposition(vector &p, vector> &c): p(p){ LCA = lowest_common_ancestor(p, c); int N = p.size(); in = vector(N, -1); sz = vector(N, -1); next = vector(N, 0); BIT = binary_indexed_tree(N); t = 0; dfs1(c); dfs2(c); } void add(int v){ BIT.add(in[v]); } T query(int u, int v){ int w = LCA.query(u, v); T ans = 0; while (next[u] != next[w]){ ans += BIT.query(in[next[u]], in[u] + 1); u = p[next[u]]; } ans += BIT.query(in[w], in[u] + 1); while (next[v] != next[w]){ ans += BIT.query(in[next[v]], in[v] + 1); v = p[next[v]]; } ans += BIT.query(in[w] + 1, in[v] + 1); return ans; } }; template struct weighted_tree_distance{ vector d; vector s; vector> next; weighted_tree_distance(vector>> &E){ int N = E.size(); d = vector(N, 0); s = vector(N, 0); next = vector>(LOG, vector(N, -1)); queue Q; Q.push(0); while (!Q.empty()){ int v = Q.front(); Q.pop(); for (auto e : E[v]){ T c = e.first; int w = e.second; if (w != next[0][v]){ next[0][w] = v; d[w] = d[v] + 1; s[w] = s[v] + c; Q.push(w); } } } for (int i = 1; i < LOG; i++){ for (int j = 0; j < N; j++){ if (next[i - 1][j] != -1){ next[i][j] = next[i - 1][next[i - 1][j]]; } } } } int lca(int u, int v){ if (d[u] < d[v]){ swap(u, v); } for (int i = 0; i < LOG; i++){ if ((d[u] - d[v]) >> i & 1){ u = next[i][u]; } } if (u == v){ return u; } else { for (int i = LOG - 1; i >= 0; i--){ if (next[i][u] != next[i][v]){ u = next[i][u]; v = next[i][v]; } } return next[0][u]; } } int dist1(int u, int v){ return d[u] + d[v] - 2 * d[lca(u, v)]; } T dist2(int u, int v){ return s[u] + s[v] - 2 * s[lca(u, v)]; } }; int main(){ int N; cin >> N; vector>> E(N); vector> edges; for (int i = 0; i < N - 1; i++){ int u, v, w; cin >> u >> v >> w; u--; v--; E[u].push_back(make_pair(w, v)); E[v].push_back(make_pair(w, u)); edges.push_back(make_tuple(w, u, v)); } vector p(N, -1); vector> c(N); vector a(N, 0); queue q; q.push(0); while (!q.empty()){ int v = q.front(); q.pop(); for (auto e : E[v]){ int d = e.first; int w = e.second; if (w != p[v]){ p[w] = v; c[v].push_back(w); a[w] = d; q.push(w); } } } int Q; cin >> Q; vector x(Q), y(Q); for (int i = 0; i < Q; i++){ cin >> x[i] >> y[i]; x[i]--; y[i]--; } sort(edges.begin(), edges.end()); vector tv(Q, N); vector fv(Q, 0); while (1){ bool upd = false; vector> check(N - 1); for (int i = 0; i < Q; i++){ if (tv[i] - fv[i] > 1){ upd = true; int mid = (tv[i] + fv[i]) / 2; check[mid - 1].push_back(i); } } if (!upd){ break; } heavy_light_decomposition T1(p, c), T2(p, c); vector used(N, false); for (int i = 0; i < N - 1; i++){ int u = get<1>(edges[i]); int v = get<2>(edges[i]); T1.add(u); T1.add(v); if (u == p[v]){ T2.add(v); used[v] = true; } else { T2.add(u); used[u] = true; } for (int id : check[i]){ int a = T1.query(x[id], y[id]); int b = T2.query(x[id], y[id]); int l = T1.LCA.query(x[id], y[id]); if (used[l]){ b--; } if (a > b * 2){ tv[id] = i + 1; } else { fv[id] = i + 1; } } } } weighted_tree_distance T(E); for (int i = 0; i < Q; i++){ if (tv[i] == N){ cout << -1 << endl; } else { cout << T.dist2(x[i], y[i]) + get<0>(edges[tv[i] - 1]) * 2 << endl; } } }