给定一棵 \(n\) 个点的树 \(T\)，边有边权。现在有 \(q\) 组询问，每组询问给出 \(l, r\)，求出： \(n \le 2 \times 10^5\), \(q \le 10^6\), \(1 \le w \le 10^9\)。题意
由于与路径长度有关，所以考虑点分治或者 LCA。由于笔者思考 LCA 无果所以这篇题解的做法是点分治。
考虑点分治，对于一个分治过程，我们考虑计算出分治块内点对对询问的贡献。对于分治块内的点 \(x\)，记 \(x\) 到分治重心的距离为 \(d_x\)。根据 Shik and Travel 的一个 trick，考虑只记录有用的点对，什么点对是有用的？对于点对 \((x, y)\)，如果不存在 \((x', y')\) 使得 \(x \le x' < y' \le y\) 且 \(d_x + d_y \ge d_{x'} + d_{y'}\)，那么 \((x, y)\) 是有用的。因为点对 \((x', y')\) 能贡献到更多的询问，并且其 \(\operatorname{dist}\) 还更小，所以 \((x, y)\) 可以被 \((x', y')\) 完全代替。当分治块内不存在更好的点对时，\((x, y)\) 就是有用的。
同时，这里不对每个点来自哪个分治重心的儿子区分，因为如果两个点属于同一个子树，在继续往下分治时这两个点的贡献会被重新计算。在当前分治过程中，即使将两点距离计算错误也不会对最终答案产生影响。
有用的点对有多少呢？观察到当 \(y' = y\) 时，有 \(d_x < d_{x'}\)，当 \(x' = x\) 时，有 \(d_y < d_{y'}\)，所以有：\(\max(d_x, d_y) < \min_{i = x + 1}^{y - 1} d_i\)。于是我们有了一个找出所有有用点对的方法：将所有点按照编号从小到大排成一个序列，对于点 \(x\)，找到左边第一个满足 \(d_l \le d_x\) 的 \(l\) 和右边第一个满足 \(d_r \le d_x\) 的 \(r\)，\((x, l)\) 和 \((x, r)\) 就是两个有用的点对。根据这个方法，我们同样证明了有用的点对数量是 \(\mathcal{O}(s)\) 的，其中 \(s\) 是分治块大小，总点对数量就是 \(\mathcal{O}(\sum s) = \mathcal{O}(n \log n)\)。
现在问题转化成对于每个询问 \((l, r)\)，找到 \(l \le x < y \le r\) 的最近有用点对，按 \(l\) / \(x\) 从大到小排序之后，扫描线+树状数组即可。总时间复杂度 \(\mathcal{O}(n \log^2 n + q\log n)\)。
代码
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
constexpr int N = 2E5 + 5, Q = 1E6 + 5;
int n, q;
std::vector<std::array<int, 2>> adj[N];
int k;
struct Data {
int x, y;
i64 d;
int type;
constexpr bool operator<(const Data& w) const {
return x == w.x ? y == w.y ? type < w.type : y < w.y : x > w.x;
}
} a[N * 60 + Q];
bool vis[N];
int siz[N], maxs[N];
int dsum, root;
i64 d[N];
i64 ans[Q];
void getroot(int x, int par) {
siz[x] = 1;
maxs[x] = 0;
for (auto [y, z] : adj[x]) {
if (y == par || vis[y]) {
continue;
}
d[y] = d[x] + z;
getroot(y, x);
siz[x] += siz[y];
maxs[x] = std::max(maxs[x], siz[y]);
}
maxs[x] = std::max(maxs[x], dsum - siz[x]);
if (!root || maxs[root] > maxs[x]) {
root = x;
}
}
void solve(int x, int nsum) {
root = 0;
dsum = nsum;
getroot(x, x);
vis[x = root] = 1;
d[root] = 0;
getroot(x, x);
std::vector<std::pair<int, i64>> vec;
auto dfs = [&](auto &&self, int x, int par) -> void {
vec.push_back({x, d[x]});
for (auto [y, z] : adj[x]) {
if (!vis[y] && y != par) {
self(self, y, x);
}
}
} ;
dfs(dfs, x, x);
int m = vec.size();
std::sort(vec.begin(), vec.end());
std::stack<int> st;
auto push = [&]() {
for (int i = 0; i < m; ++i) {
while (!st.empty() && vec[st.top()].second >= vec[i].second) {
a[++k] = {vec[st.top()].first, vec[i].first, vec[st.top()].second + vec[i].second, 0};
st.pop();
}
st.push(i);
}
while (!st.empty()) {
st.pop();
}
} ;
push();
std::reverse(vec.begin(), vec.end());
push();
for (auto [y, z] : adj[x]) {
if (!vis[y]) {
solve(y, siz[y]);
}
}
}
struct Fenwick {
i64 c[N];
Fenwick() {
for (int i = 0; i < N; ++i) {
c[i] = 1E15;
}
}
void insert(int x, i64 val) {
for (; x <= n; x += x & -x)
c[x] = std::min(c[x], val);
}
i64 query(int x) {
i64 res = 1E15;
for (; x; x -= x & -x) {
res = std::min(res, c[x]);
}
return res;
}
} fen;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1; i < n; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
solve(1, n);
for (int i = 1; i <= k; ++i) {
if (a[i].x > a[i].y) std::swap(a[i].x, a[i].y);
}
std::cin >> q;
for (int i = 1; i <= q; ++i) {
int l, r;
std::cin >> l >> r;
a[++k] = {l, r, i, 1};
}
std::sort(a + 1, a + 1 + k);
for (int i = 1; i <= k; ++i) {
if (a[i].type == 1) ans[a[i].d] = fen.query(a[i].y);
else fen.insert(a[i].y, a[i].d);
}
for (int i = 1; i <= q; ++i) {
std::cout << (ans[i] == 1E15 ? -1 : ans[i]) << "\n";
}
return 0;
}