#include #include #include using namespace std; #pragma warning (disable: 4996) // 入力 long long N, A[1 << 18], B[1 << 18], C[1 << 18]; long long Q, X[1 << 18], Y[1 << 18]; // 出力 long long Answer[1 << 18]; // グラフ vector> G[1 << 18]; vector> H[1 << 18]; vector I; int dp[1 << 18]; int col[1 << 18]; int representative[1 << 18]; long long par[1 << 18]; long long dist[1 << 18]; long long dist2[1 << 18]; void dfs1(int pos) { dp[pos] = 1; for (int i = 0; i < G[pos].size(); i++) { if (dp[G[pos][i].first] >= 1) continue; dfs1(G[pos][i].first); dp[pos] += dp[G[pos][i].first]; } } void dfs2(int pos, int pre, int cols, long long dep, long long dep2) { col[pos] = cols; dist[pos] = dep; dist2[pos] = dep2; par[pos] = pre; for (int i = 0; i < G[pos].size(); i++) { if (G[pos][i].first == pre) continue; long long new_dep2 = dep2; for (int j = 0; j < H[pos].size(); j++) { if (H[pos][j].second == pre) continue; if (H[pos][j].second == G[pos][i].first) continue; new_dep2 = min(new_dep2, H[pos][j].first); break; } dfs2(G[pos][i].first, pos, cols, dep + C[G[pos][i].second], new_dep2); I.push_back(G[pos][i].second); } } void solve(vector E, vector D) { if (D.size() == 0) return; // Step A: 前処理 vector F; for (int i : E) { F.push_back(A[i]); F.push_back(B[i]); G[A[i]].push_back(make_pair(B[i], i)); G[B[i]].push_back(make_pair(A[i], i)); } sort(F.begin(), F.end()); F.erase(unique(F.begin(), F.end()), F.end()); // Step B. 重心を見つける dfs1(E[0]); int grav = -1, minx = (1 << 30); for (int i : F) { int rem = F.size() - 1, maxv = 0; for (int j = 0; j < G[i].size(); j++) { int to = G[i][j].first; if (dp[to] > dp[i]) continue; maxv = max(maxv, dp[to]); rem -= dp[to]; } maxv = max(maxv, rem); if (minx > maxv) { minx = maxv; grav = i; } } // Step C: 深さ優先探索 int cnts = 0; vector> J; dist[grav] = 0; dist2[grav] = (1LL << 60); for (int i = 0; i < G[grav].size(); i++) { cnts++; int to = G[grav][i].first; int idx = G[grav][i].second; representative[cnts] = to; I.clear(); dfs2(to, grav, cnts, C[idx], 1LL << 60); J.push_back(I); } // Step D: クエリに答える vector> K(cnts, vector(0, 0)); for (int idx : D) { if (col[X[idx]] == col[Y[idx]]) { K[col[X[idx]] - 1].push_back(idx); continue; } long long d1 = dist[X[idx]] + dist[Y[idx]]; long long d2 = dist2[X[idx]]; long long d3 = dist2[Y[idx]]; long long d4 = (1LL << 60), d5 = (1LL << 60), d6 = (1LL << 60); if (X[idx] != grav) { for (int i = 0; i < H[X[idx]].size(); i++) { if (H[X[idx]][i].second == par[X[idx]]) continue; d4 = H[X[idx]][i].first; break; } } if (Y[idx] != grav) { for (int i = 0; i < H[Y[idx]].size(); i++) { if (H[Y[idx]][i].second == par[Y[idx]]) continue; d5 = H[Y[idx]][i].first; break; } } for (int i = 0; i < H[grav].size(); i++) { if (H[grav][i].second == representative[col[X[idx]]]) continue; if (H[grav][i].second == representative[col[Y[idx]]]) continue; d6 = H[grav][i].first; break; } Answer[idx] = d1 + 2LL * min({ d2, d3, d4, d5, d6 }); if (Answer[idx] >= (1LL << 60)) Answer[idx] = -1; } // Step E: 初期化 for (int i : F) { dp[i] = 0; col[i] = 0; dist[i] = 0; dist2[i] = 0; par[i] = 0; G[i].clear(); } for (int i = 1; i <= cnts; i++) representative[i] = 0; // Step F: 木の分解 for (int i = 0; i < cnts; i++) { solve(J[i], K[i]); } } int main() { // Step #1. 入力 scanf("%lld", &N); for (int i = 1; i <= N - 1; i++) { scanf("%lld%lld%lld", &A[i], &B[i], &C[i]); H[A[i]].push_back(make_pair(C[i], B[i])); H[B[i]].push_back(make_pair(C[i], A[i])); } scanf("%lld", &Q); for (int i = 1; i <= Q; i++) scanf("%lld%lld", &X[i], &Y[i]); for (int i = 1; i <= N; i++) sort(H[i].begin(), H[i].end()); // Step #2. 重心分解 vector E, D; for (int i = 1; i <= N - 1; i++) E.push_back(i); for (int i = 1; i <= Q; i++) D.push_back(i); solve(E, D); // Step #3. 出力 for (int i = 1; i <= Q; i++) printf("%lld\n", Answer[i]); return 0; }