类比 P9062 [Ynoi2002] Adaptive Hsearch&Lsearch 处理区间最近点对的思路，尝试只保留可能有贡献的点对。
处理树上路径容易想到点分治。设点 \(u\) 到分治中心的距离为 \(a_u\)。我们有 \(\text{dis}(u, v) \le a_u + a_v\)。
考虑一个点对 \((u, v)\) 什么时候一定没贡献。这里默认 \(u, v\) 跨过分治中心，若不跨过并且在这一层舍弃了还可以在下一层重新被考虑。若存在 \(w \in [u + 1, v - 1]\) 使得 \(\text{dis}(u, w) \le a_u + a_v\) 且 \(\text{dis}(w, v) \le a_u + a_v\) 那么 \((u, v)\) 就没用，放缩一下有 \(a_w \le a_v\) 且 \(a_w \le a_u\)。所以一个点对 \((u, v)\) 要满足 \(\max(a_u, a_v) < \min\limits_{i = u + 1}^{v - 1} a_i\) 才可能有贡献。
分类讨论一下。如果 \(a_u \le a_v\)，那么 \(u\) 必须是 \(v\) 之前第一个比 \(a_u\) 小的点，用单调栈求一下即可。如果 \(a_u \ge a_v\) 那么 \(v\) 必须是 \(u\) 之后第一个比 \(a_v\) 小的点，倒着再做一遍即可。
根据上面的求法我们可以得到有贡献点对数量是 \(O(n \log n)\) 的。
接下来就是套路的扫描线了。扫右端点 \(r\)，每次把 \(v = r\) 的点对加入。那么一次询问 \(l\) 就是查询 \([l, n]\) 的后缀最小值。树状数组维护即可。
总时间复杂度是 \(O(n \log^2 n + q \log n)\)。
code
// Problem: P9058 [Ynoi2004] rpmtdq
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9058
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
namespace IO {
char ibuf[1 << 20], *iS, *iT, obuf[1 << 20], *oS = obuf;
#define writesp(x) write(x), pc(' ')
#define writeln(x) write(x), pc('\n')
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 20, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
template<typename T = int>
inline T read() {
char ch = gh();
T x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void flush () {
fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
}
inline void pc (char ch) {
if (oS == obuf + (1 << 20)) flush();
*oS++ = ch;
}
template<typename _Tp>
inline void write (_Tp x) {
static char stk[64], *tp = stk;
if (x < 0) x = ~(x - 1), pc('-');
do *tp++ = x % 10, x /= 10;
while (x);
while (tp != stk) pc((*--tp) | 48);
}
}
using IO::read;
using IO::write;
using IO::pc;
using IO::flush;
const int maxn = 200100;
const int logn = 20;
const int maxm = 1000100;
ll n, m, ans[maxm], stk[maxn], dep[maxn];
int st[logn][maxn], dfn[maxn], tim;
vector<pii> G[maxn], qq[maxn];
vector<int> vc[maxn];
ll f[maxn], sz[maxn], rt, tot;
pii a[maxn];
bool vis[maxn];
void dfs2(int u, int fa, int t) {
f[u] = sz[u] = 1;
for (pii p : G[u]) {
ll v = p.fst;
if (v == fa || vis[v]) {
continue;
}
dfs2(v, u, t);
sz[u] += sz[v];
f[u] = max(f[u], sz[v]);
}
f[u] = max(f[u], t - sz[u]);
if (!rt || f[u] < f[rt]) {
rt = u;
}
}
void dfs3(int u, int fa, ll t) {
a[++tot] = mkp(u, t);
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (v == fa || vis[v]) {
continue;
}
dfs3(v, u, t + d);
}
}
void dfs(int u) {
vis[u] = 1;
tot = 0;
dfs3(u, -1, 0);
sort(a + 1, a + tot + 1);
int top = 0;
for (int i = 1; i <= tot; ++i) {
while (top && a[stk[top]].scd > a[i].scd) {
--top;
}
if (top) {
vc[a[i].fst].pb(a[stk[top]].fst);
}
stk[++top] = i;
}
top = 0;
for (int i = tot; i; --i) {
while (top && a[stk[top]].scd > a[i].scd) {
--top;
}
if (top) {
vc[a[stk[top]].fst].pb(a[i].fst);
}
stk[++top] = i;
}
for (pii p : G[u]) {
ll v = p.fst;
if (vis[v]) {
continue;
}
rt = 0;
dfs2(v, u, sz[v]);
dfs2(rt, -1, sz[v]);
dfs(rt);
}
}
void dfs4(int u, int fa) {
dfn[u] = ++tim;
st[0][tim] = fa;
for (pii p : G[u]) {
ll v = p.fst, d = p.scd;
if (v == fa) {
continue;
}
dep[v] = dep[u] + d;
dfs4(v, u);
}
}
inline int get(int i, int j) {
return dfn[i] < dfn[j] ? i : j;
}
inline int qlca(int x, int y) {
x = dfn[x];
y = dfn[y];
if (x > y) {
swap(x, y);
}
++x;
int k = __lg(y - x + 1);
return get(st[k][x], st[k][y - (1 << k) + 1]);
}
inline ll qdis(int x, int y) {
return dep[x] + dep[y] - dep[qlca(x, y)] * 2;
}
namespace BIT {
ll c[maxn];
inline void init() {
mems(c, 0x3f);
}
inline void update(ll x, ll d) {
for (int i = x; i; i -= (i & (-i))) {
c[i] = min(c[i], d);
}
}
inline ll query(ll x) {
ll res = 9e18;
for (int i = x; i <= n; i += (i & (-i))) {
res = min(res, c[i]);
}
return res;
}
}
void solve() {
n = read();
for (int i = 1, u, v, d; i < n; ++i) {
u = read();
v = read();
d = read();
G[u].pb(v, d);
G[v].pb(u, d);
}
m = read();
for (int i = 1, l, r; i <= m; ++i) {
l = read();
r = read();
if (l >= r) {
ans[i] = -1;
continue;
}
qq[r].pb(l, i);
}
dfs2(1, -1, n);
dfs2(rt, -1, n);
dfs(rt);
dfs4(1, 0);
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
BIT::init();
for (int i = 1; i <= n; ++i) {
for (int j : vc[i]) {
BIT::update(j, qdis(i, j));
}
for (pii p : qq[i]) {
ans[p.scd] = BIT::query(p.fst);
}
}
for (int i = 1; i <= m; ++i) {
writeln(ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
flush();
return 0;
}