#pragma GCC target ("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ld = long double; #define all(a) (a).begin(),(a).end() #define fs first #define sc second #define xx first #define yy second.first #define zz second.second #define H pair #define P pair> #define Q(i,j,k) mkp(i,mkp(j,k)) #define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++) #define rep(i,n) rng(i, 0, (n)) #define mkp make_pair #define vec vector #define vi vec #define pb emplace_back #define siz(a) (int)(a).size() #define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end()) #define getidx(b,i) (lower_bound(all(b),(i))-(b).begin()) #define ssp(i,n) (i==(ll)(n)-1?"\n":" ") #define ctoi(c) (int)(c-'0') #define itoc(c) (char)(c+'0') #define cyes printf("Yes\n") #define cno printf("No\n") #define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--) #define gcj printf("Case #%lld: ",qq123_+1) #define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read() #define found(a,x) (a.find(x)!=a.end()) constexpr ll mod = (ll)1e9 + 7; constexpr ll Mod = 998244353; constexpr ld EPS = 1e-10; constexpr ll inf = (ll)3 * 1e18; constexpr int Inf = (ll)15 * 1e8; constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 }; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } ll read() { ll u, k = scanf("%lld", &u); return u; } string reads() { string s; cin >> s; return s; } H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; } bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; } bool ina(int t, int l, int r) { return l <= t && t < r; } ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; } ll popcount(ll x) { int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++; return sum; } template class csum { vec v; public: csum(vec& a) :v(a) { build(); } csum() {} void init(vec& a) { v = a; build(); } void build() { for (int i = 1; i < v.size(); i++) v[i] += v[i - 1]; } T a(int l, int r) { if (r < l) return 0; return v[r] - (l == 0 ? 0 : v[l - 1]); }//[l,r] T b(int l, int r) { return a(l, r - 1); }//[l,r) T a(pairt) { return a(t.first, t.second); } T b(pairt) { return b(t.first, t.second); } }; class mint { public:ll v; mint(ll v = 0) { s(v % mod + mod); } constexpr static int mod = (ll)1e9 + 7; constexpr static int fn_ = (ll)2e6 + 5; static mint fact[fn_], comp[fn_]; mint pow(int x) const { mint b(v), c(1); while (x) { if (x & 1) c *= b; b *= b; x >>= 1; } return c; } inline mint& s(int vv) { v = vv < mod ? vv : vv - mod; return *this; } inline mint inv()const { return pow(mod - 2); } inline mint operator-()const { return mint() - *this; } inline mint& operator+=(const mint b) { return s(v + b.v); } inline mint& operator-=(const mint b) { return s(v + mod - b.v); } inline mint& operator*=(const mint b) { v = v * b.v % mod; return *this; } inline mint& operator/=(const mint b) { v = v * b.inv().v % mod; return *this; } inline mint operator+(const mint b) const { return mint(v) += b; } inline mint operator-(const mint b) const { return mint(v) -= b; } inline mint operator*(const mint b) const { return mint(v) *= b; } inline mint operator/(const mint b) const { return mint(v) /= b; } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; } friend istream& operator>>(istream& is, mint& m) { int x; is >> x; m = mint(x); return is; } bool operator<(const mint& r)const { return v < r.v; } bool operator>(const mint& r)const { return v > r.v; } bool operator<=(const mint& r)const { return v <= r.v; } bool operator>=(const mint& r)const { return v >= r.v; } bool operator==(const mint& r)const { return v == r.v; } bool operator!=(const mint& r)const { return v != r.v; } explicit operator bool()const { return v; } explicit operator int()const { return v; } mint comb(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { if (k > * this - k) k = *this - k; mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp * comp[k.v]; } return fact[v] * comp[k.v] * comp[v - k.v]; }//nCk mint perm(mint k) { if (k > * this) return mint(); if (!fact[0]) combinit(); if (v >= fn_) { mint tmp(1); for (int i = v; i >= v - k.v + 1; i--) tmp *= mint(i); return tmp; } return fact[v] * comp[v - k.v]; }//nPk static void combinit() { fact[0] = 1; for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * mint(i); comp[fn_ - 1] = fact[fn_ - 1].inv(); for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * mint(i + 1); } }; mint mint::fact[fn_], mint::comp[fn_]; //-------------------------------------------------------------- auto RUQ = [](ll& num, ll x, int width) {num = x; }; auto RAQ = [](ll& num, ll x, int width) {num += x; }; auto RCMXQ = [](ll& num, ll x, int width) {num = max(num, x); }; auto RCMNQ = [](ll& num, ll x, int width) {num = min(num, x); }; auto RASQ = [](ll& num, ll x, int width) {num += (x * width); }; auto RUSQ = [](ll& num, ll x, int width) {num = (x * width); }; auto RSQ = [](ll x, ll y)->ll {return x + y; }; auto RMXQ = [](ll x, ll y)->ll {return max(x, y); }; auto RMNQ = [](ll x, ll y)->ll {return min(x, y); }; class Segtree { #define SEG_SIZE 900000 using F = function; using T = function; int siz, rr; ll zer, zer2; ll dat[SEG_SIZE], lazy[SEG_SIZE]; bool updated[SEG_SIZE]; F upd; T qur; public: //for update, for query void init(int size, F update, T query, ll zero, ll zero2) { siz = size, upd = update, qur = query, zer = zero2, zer2 = zero; rr = 1; while (rr < size) rr *= 2; for (int i = 0; i < SEG_SIZE; i++) dat[i] = zer, lazy[i] = zer2, updated[i] = 0; } void rmnq(int n) { init(n, RUQ, RMNQ, 0, inf); } void rmxq(int n) { init(n, RUQ, RMXQ, 0, -inf); } template void build(const Iterator st, const Iterator ed) { Iterator it = st; int cur = rr - 1; while (it != ed) dat[cur++] = (*it++); for (int i = rr - 2; i >= 0; i--) dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } void build(vectorv) { for (int i = 0; i < min((int)v.size(), siz); i++) dat[i + rr - 1] = v[i]; for (int i = rr - 2; i >= 0; i--) dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } void update(int a, int b, ll x) { update(0, a, b, 0, rr, x); } ll query(int a, int b) { return query(0, a, b, 0, rr); } ll lower_bound(int a, int b, functioncomp) { return lower_bound(0, a, b, 0, rr, comp); } ll upper_bound(int a, int b, functioncomp) { return upper_bound(0, a, b, 0, rr, comp); } ll operator[](const int i) { return query(i, i + 1); } private: void eval(int i, int l, int r) { if (!updated[i]) return; if (r - l > 1) { upd(lazy[i * 2 + 1], lazy[i], 1); upd(lazy[i * 2 + 2], lazy[i], 1); updated[i * 2 + 1] = updated[i * 2 + 2] = 1; } upd(dat[i], lazy[i], min(r, siz) - l); lazy[i] = zer2; updated[i] = 0; } void update(int i, int a, int b, int l, int r, ll x) { eval(i, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { upd(lazy[i], x, 1); updated[i] = 1; eval(i, l, r); return; } update(i * 2 + 1, a, b, l, (l + r) / 2, x); update(i * 2 + 2, a, b, (l + r) / 2, r, x); dat[i] = qur(dat[i * 2 + 1], dat[i * 2 + 2]); } ll query(int i, int a, int b, int l, int r) { eval(i, l, r); if (b <= l || r <= a) return zer; if (a <= l && r <= b) return dat[i]; return qur(query(i * 2 + 1, a, b, l, (l + r) / 2), query(i * 2 + 2, a, b, (l + r) / 2, r)); } ll lower_bound(int i, int a, int b, int l, int r, functioncomp) { eval(i, l, r); if (b <= l || r <= a || !comp(dat[i])) return b; if (r - l == 1) return l; ll tmp = lower_bound(i * 2 + 1, a, b, l, (l + r) / 2, comp); if (tmp < b) return tmp; return lower_bound(i * 2 + 2, a, b, (l + r) / 2, r, comp); } ll upper_bound(int i, int a, int b, int l, int r, functioncomp) { eval(i, l, r); if (b <= l || r <= a || !comp(dat[i])) return a - 1; if (r - l == 1) return l; ll tmp = upper_bound(i * 2 + 2, a, b, (l + r) / 2, r, comp); if (tmp >= a) return tmp; return upper_bound(i * 2 + 1, a, b, l, (l + r) / 2, comp); } }; class HLD { #define HLD_SIZ 400010 using F = function; using T = function; int n, st, idx; ll zer, zer2; bool mde; int siz[HLD_SIZ]; vectore[HLD_SIZ]; vector>>f; int in[HLD_SIZ], out[HLD_SIZ], rev[HLD_SIZ]; int head[HLD_SIZ], prt[HLD_SIZ], dept[HLD_SIZ]; Segtree seg; F upd; T qur; public: //for update, for query, mode(0:vertex, 1:edge) void init(int size, F update, T query, ll zero, ll zero2, bool mode) { n = size, zero = zer, zer2 = zero2; upd = update, qur = query; mde = mode; idx = 0; f.clear(); for (int i = 0; i <= n; i++) { siz[i] = 0, prt[i] = -1, head[i] = -1; in[i] = 0, out[i] = 0, rev[i] = 0; dept[i] = 0; e[i].clear(); } } void add_edge(int u, int v, ll r) { add_edge(u, v); f.pb(make_pair(u, make_pair(v, r))); } void add_edge(int u, int v) { e[u].pb(v); e[v].pb(u); } void build(int root = 0) { st = root; dept[st] = 0; for (auto u : e[st]) normalize(u, st, 1); for (int i = 0; i <= n; i++) if (i != st && !(~prt[i])) { dept[i] = 0; for (auto u : e[i]) normalize(u, i, 1); } for (int i = 0; i <= n; i++) if (!(~prt[i])) dfs1(i); for (int i = 0; i <= n; i++) if (!(~prt[i])) { head[i] = i; dfs2(i); } seg.init(idx, upd, qur, zer, zer2); if (f.size()) { vectorv(idx, zer2); for (auto g : f) { v[max(in[g.fs], in[g.sc.fs])] = g.sc.sc; } seg.build(v); } } void update(int a, int b, ll x) { while (head[a] != head[b]) { if (in[a] > in[b]) swap(a, b); seg.update(in[head[b]], in[b] + 1, x); b = prt[head[b]]; } if (in[a] > in[b]) swap(a, b); seg.update(in[a] + mde, in[b] + 1, x); } ll query(int a, int b) { ll ret = zer2; while (head[a] != head[b]) { if (in[a] > in[b]) swap(a, b); ret = qur(ret, seg.query(in[head[b]], in[b] + 1)); b = prt[head[b]]; } if (in[a] > in[b]) swap(a, b); ret = qur(ret, seg.query(in[a] + mde, in[b] + 1)); return ret; } int lca(int a, int b) { while (1) { if (in[a] > in[b]) swap(a, b); if (head[a] == head[b]) return a; b = prt[head[b]]; } } void subupdate(int a, ll x) { seg.update(in[a], out[a], x); } ll subquery(int a) { return seg.query(in[a], out[a]); } int par(int x, int t) { while (~x) { if (in[x] - in[head[x]] >= t) return rev[in[head[x]] + ((in[x] - in[head[x]]) - t)]; t -= (in[x] - in[head[x]] + 1); x = prt[head[x]]; } return x; } ll operator[](const int& i) { return dept[i]; } ll lower_bound(int a, int b, functioncomp) { vectorleft, right; bool swapped = 0; while (head[a] != head[b]) { if (in[a] > in[b]) { swap(a, b); swapped = !swapped; } if (swapped) left.push_back(H{ in[head[b]], in[b] + 1 }); else right.push_back(H{ in[head[b]],in[b] + 1 }); b = prt[head[b]]; } //swap=0の時は終点を縮める、 if (in[a] > in[b]) { swap(a, b); swapped = !swapped; } //leftはupper_boundで、rightはlower_boundで求める ll tmp = zer2, r; for (auto g : left) { r = seg.upper_bound(g.fs, g.sc, [&](int a) {return comp(qur(tmp, a)); }); if (r != g.fs - 1) return rev[r]; tmp = qur(tmp, seg.query(g.fs, g.sc)); } if (swapped) { r = seg.upper_bound(in[a] + mde, in[b] + 1, [&](int a) {return comp(qur(tmp, a)); }); if (r != in[a] + mde - 1) return rev[r]; tmp = qur(tmp, seg.query(in[a] + mde, in[b] + 1)); } else { r = seg.lower_bound(in[a] + mde, in[b] + 1, [&](int a) {return comp(qur(tmp, a)); }); if (r != in[b] + 1) return rev[r]; tmp = qur(tmp, seg.query(in[a] + mde, in[b] + 1)); } for (auto g : right) { r = seg.lower_bound(g.fs, g.sc, [&](int a) {return comp(qur(tmp, a)); }); if (r != g.sc) return rev[r]; tmp = qur(tmp, seg.query(g.fs, g.sc)); } return -1; }//区間[a,b]で、qurの値がcompになる最初の点を求める private: void normalize(int v, int p, int d) { dept[v] = d; prt[v] = p; for (auto& u : e[v]) { if (u == e[v].back()) break; if (u == p) swap(u, e[v].back()); normalize(u, v, d + 1); } if (!e[v].empty()) e[v].pop_back(); } void dfs1(int v) { siz[v] = 1; for (int& u : e[v]) { dfs1(u); siz[v] += siz[u]; if (siz[u] > siz[e[v][0]]) { swap(u, e[v][0]); } } } void dfs2(int v) { rev[idx] = v; in[v] = idx++; for (auto u : e[v]) { head[u] = (u == e[v][0] ? head[v] : u); dfs2(u); } out[v] = idx; } }; //--------------------------------------------------------------------- int n; vec

e[200000]; ll pa[200000]; Segtree seg; HLD hld, hld2; mapf[200000]; void dfs(int x, int p) { for (auto g : e[x]) { if (g.xx == p) continue; pa[g.xx] = g.yy; dfs(g.xx, x); } } signed main() { cin >> n; hld.init(n, RUQ, RMNQ, 0, inf, 1); hld2.init(n, RUSQ, RSQ, 0, 0, 1); rep(i, n - 1) { int u, v; ll r; cin >> u >> v >> r; u--; v--; f[u][v] = siz(e[v]); f[v][u] = siz(e[u]); e[u].pb(Q( v,r,siz(e[v]) )); e[v].pb(Q( u,r,siz(e[u]) - 1 )); hld.add_edge(u, v); hld2.add_edge(u, v, r); } hld.build(); hld2.build(); veca; int sum = 0; vi v; rep(i, n) { a.pb(H{ sum,sum + siz(e[i]) }); for (auto g : e[i]) { if (g.xx == hld.par(i, 1)) v.pb(inf); else v.pb(g.yy); } sum += siz(e[i]); pa[i] = inf; } seg.init(siz(v), RUQ, RMNQ, inf, inf); seg.build(v); rng(i, 1, n) { for (auto g : e[i]) { if (g.xx == hld.par(i, 1)) { int r = hld.par(i, 1); ll t = min(seg.query(a[r].fs, a[r].fs + g.zz), seg.query(a[r].fs + g.zz + 1, a[r].sc)); hld.update(i, r, t); } } } dfs(0, -1); cdf(read()) { int u, v; cin >> u >> v; u--; v--; int t = hld.lca(u, v); ll mn = inf; auto F = [&](int u) { if (hld[u] - hld[t] > 1) { chmin(mn, hld.query(t, hld.par(u, hld[u] - hld[t] - 1))); } }; F(u); F(v); auto G = [&](int u) { if (u != t) { chmin(mn, seg.query(a[u].fs, a[u].sc)); } }; G(u); G(v); if (u == t) swap(u, v); int g = hld.par(u, max(0ll, hld[u] - hld[t] - 1)); int c = a[t].fs + f[g][t]; chmin(mn, pa[t]); if (v == t) { chmin(mn, min(seg.query(a[t].fs, c), seg.query(c + 1, a[t].sc))); } else { int d = a[t].fs + f[hld.par(v, max(0ll, hld[v] - hld[t] - 1))][t]; if (c > d) swap(c, d); chmin(mn, min(seg.query(a[t].fs, c), min(seg.query(c + 1, d), seg.query(d + 1, a[t].sc)))); } if (mn == inf) { cout << -1 << endl; } else { cout << hld2.query(u, v) + 2 * mn << endl; } } }