//#define _GLIBCXX_DEBUG #include #define rep(i, n) for(int i=0; i; using vs = vector; using vi = vector; using vvi = vector; template using PQ = priority_queue; template using PQG = priority_queue, greater >; const int INF = 0xccccccc; const ll LINF = 922337203685477580LL; template inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);} template inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);} template istream &operator>>(istream &is, pair &p) { return is >> p.first >> p.second;} template ostream &operator<<(ostream &os, const pair &p) { return os << p.first << ' ' << p.second;} template struct lca { int n, root, l; vector > to, par; vector > co; vector dep; vector costs; lca(int n):n(n), to(n), co(n), dep(n), costs(n) { l = 0; while((1< >(n+1, vector(l, n)); } void add(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if(p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for(int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if(u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for(int i = 0; i < l-1; ++i) { for(int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } int lca_(int a, int b) { if(dep[a] > dep[b]) swap(a, b); int gap = dep[b]-dep[a]; for(int i = l-1; i >= 0; --i) { int len = 1<= len) { gap -= len; b = par[b][i]; } } if(a == b) return a; for(int i = l-1; i >= 0; --i) { int na = par[a][i]; int nb = par[b][i]; if(na != nb) { a = na; b = nb; } } return par[a][0]; } int length(int a, int b) { int c = lca_(a, b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = lca_(a, b); return costs[a]+costs[b]-costs[c]*2; } }; template struct SegTree { using FX = function; int n; FX fx; const T ex; vector dat; SegTree(int n_, FX fx_, T ex_):fx(fx_), ex(ex_), n(1) { while(n < n_) n <<= 1; dat.assign((n<<1)-1, ex); } inline int chld(int k) {return (k<<1)+1;} inline int chrd(int k) {return (k<<1)+2;} void update(int i, T x) { i += n-1; dat[i] = x; while(i) { i = (i-1)>>1; dat[i] = fx(dat[chld(i)], dat[chrd(i)]); } } inline T query(int a, int b) {return query(a, b, 0, 0, n);} T query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return ex; if(a <= l && r <= b) return dat[k]; T vl = query(a, b, chld(k), l, (l+r)>>1); T vr = query(a, b, chrd(k), (l+r)>>1, r); return fx(vl, vr); } const T &operator[](int idx) const {return dat[idx+n-1];} }; struct edge { int to, cost; }; #define N 100100 //head int n; vector G[N]; int q; int x[N], y[N], z[N]; vi dat1[N]; vector

dat2[N]; queue info1[N], info2[N]; lca L(N); SegTree rng(N, [](const int i, const int j)->int{return min(i, j);}, 0x7fffffff); void dfs(int i=0, int j=-1) { list

lst; for(edge &e:G[i]) { int ne = e.to; list

::iterator itr = lst.begin(); while(true) { if(itr == lst.end()) { if(lst.size() < 3) { lst.emplace_back(e.cost, ne); } break; } if(itr->first > e.cost) { lst.emplace(itr, e.cost, ne); if(lst.size() > 3) lst.pop_back(); break; } itr = next(itr); } } while(lst.size() < 3) lst.emplace_back(0x7fffffff, -10); for(edge &e:G[i]) { int ne = e.to; if(ne == j) continue; list

::iterator itr = lst.begin(); while(itr->second == j or itr->second == ne) itr = next(itr); rng.update(L.dep[i], itr->first); dfs(ne, i); } for(int x:dat1[i]) { if(x == i) { info1[i].emplace(0x7fffffff); continue; } list

::iterator itr = lst.begin(); while(itr->second == j) itr = next(itr); if(L.dep[i]-1 == L.dep[x]) { info1[i].emplace(itr->first); } else { info1[i].emplace(min(itr->first, rng.query(L.dep[x]+1, L.dep[i]))); } } for(P x:dat2[i]) { list

::iterator itr = lst.begin(); while(true) { if(itr->second == -10) break; int u = L.lca_(x.first, itr->second); int v = L.lca_(x.second, itr->second); if((u != i and u != j) or (v != i and v != j)) { itr = next(itr); continue; } break; } info2[i].emplace(itr->first); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; rep(i, n-1) { int u, v, w; cin >> u >> v >> w; u--; v--; L.add(u, v, w); G[u].emplace_back((edge){v, w}); G[v].emplace_back((edge){u, w}); } L.init(); cin >> q; rep(i, q) { cin >> x[i] >> y[i]; x[i]--; y[i]--; z[i] = L.lca_(x[i], y[i]); dat1[x[i]].emplace_back(z[i]); dat1[y[i]].emplace_back(z[i]); dat2[z[i]].emplace_back(x[i], y[i]); } dfs(); rep(i, q) { //cout << P(info1[x[i]].front(), info1[y[i]].front()) << ' ' << info2[z[i]].front() << endl; int u = min({info1[x[i]].front(), info1[y[i]].front(), info2[z[i]].front()}); info1[x[i]].pop(); info1[y[i]].pop(); info2[z[i]].pop(); if(u == 0x7fffffff) cout << "-1\n"; else cout << u*2+L.dist(x[i], y[i]) << '\n'; //cout << L.dist(x[i], y[i]) << "\n\n"; } }