支配点对实在是太有意思了。
本质上就是一个合法的减枝。
思路
考虑维护树上路径问题。
容易想到点分治。
考虑在当前的分治中心 \(\text{rt}\)，每个点到当前分治中心的距离为 \(dp_x\)。
求出每一组点对的贡献。
假设每个点对在距离长的那部分贡献，即 \(dp_i>dp_j\)，求出所有的 \(j\)。
结论：每个点只需要求出符合条件下的前驱后继即可。
如何证明。
假设有 \(dp_j,dp_k<dp_i\)，\(k<j<i\)。
那么如果选了 \(i,k\) 两点，那么是绝对不如选 \(j,k\) 两点的。
后继同理。
那么我们只要在点分治时。
用一个单调栈来维护这个东西。
我们按节点编号从小到大，从大到小排序做两次，维护一个单调不降的单调栈。
每个点的前驱后继就是把它弄出栈的那个点。
把所有点对扯出来以后，可以使用扫描线和树状数组维护。
代码很好写。
Code
/**
* @file P9058.cpp
* @author mfeitveer
* @date 2023-11-25
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 1000010;
const int mod = 998244353;
int n, m, rt, rtsz;
int sz[N], mz[N], vs[N];
i64 t[N], dp[N], ans[N];
vector<int> son;
vector<pair<int, i64>> to[N], que[N];
vector<tuple<int, int, i64>> fin;
inline int lb(int x)
{ return x & (-x); }
inline void upd(int x, i64 v)
{ while(x <= n) t[x] = min(t[x], v), x += lb(x); }
inline i64 ask(int x)
{ i64 res = 1e17; while(x) res = min(res, t[x]), x -= lb(x); return res; }
inline void frt(int x, int fa = 0)
{
sz[x] = 1, mz[x] = 0;
for(auto [y, w] : to[x])
{
if(y == fa || vs[y]) continue;
frt(y, x), sz[x] += sz[y];
mz[x] = max(mz[x], sz[y]);
}
mz[x] = max(mz[x], rtsz - sz[x]);
if(mz[x] < mz[rt]) rt = x;
}
inline void dfs(int x, int fa = 0)
{
son.eb(x), sz[x] = 1;
for(auto [y, w] : to[x])
{
if(y == fa || vs[y]) continue;
dp[y] = dp[x] + w, dfs(y, x);
sz[x] += sz[y];
}
}
inline void calc(int x)
{
son.clear(), dp[x] = 0, dfs(x);
sort(son.begin(), son.end());
static int stk[N]; int top = 0;
for(auto i : son)
{
while(top && dp[stk[top]] > dp[i])
fin.eb(stk[top], i, dp[stk[top]] + dp[i]), top--;
stk[++top] = i;
}
top = 0;
sort(son.begin(), son.end(), greater<>());
for(auto i : son)
{
while(top && dp[stk[top]] > dp[i])
fin.eb(stk[top], i, dp[stk[top]] + dp[i]), top--;
stk[++top] = i;
}
}
inline void solve(int x)
{
vs[x] = 1, calc(x);
for(auto [y, w] : to[x])
{
if(vs[y]) continue;
rt = 0, rtsz = sz[y], frt(y), solve(rt);
}
}
inline void solve()
{
cin >> n;
fro(i, 1, n - 1)
{
int x, y, w;
cin >> x >> y >> w;
to[x].eb(y, w), to[y].eb(x, w);
}
rtsz = mz[0] = n, frt(1), solve(rt);
memset(t, 0x3f, sizeof t);
cin >> m;
fro(i, 1, m)
{
int l, r;
cin >> l >> r;
que[l].eb(r, i);
}
fro(i, 1, n) to[i].clear();
for(auto [x, y, w] : fin)
{
if(x > y) swap(x, y);
to[x].eb(y, w);
}
pre(i, n, 1)
{
for(auto [x, w] : to[i])
upd(x, w);
for(auto [x, id] : que[i])
ans[id] = ask(x);
}
fro(i, 1, m)
cout << (ans[i] == 1e17 ? -1 : ans[i]) << "\n";
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
solve();
return 0;
}