一棵带边权的树，多次询问 $x$ 到编号为 $[l,r]$ 的点最短距离是多少
$n leq 100000$
sol：
动态点分治，每层重心维护到所有点的距离
查询的时候在管辖这个点的 log 层线段树里查就可以了
因为这样每一层的答案只会漏而不会错，所以正确性有保障
不会写点分治了...orz
#include <bits/stdc++.h> #define LL long long #define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i) #define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i) using namespace std; inline int read() { int x = 0, f = 1; char ch; for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int maxn = 200010, inf = 1e9; int n, m; int first[maxn], to[maxn << 1], nx[maxn << 1], val[maxn], cnt; inline void add(int u, int v, int w) { to[++cnt] = v; val[cnt] = w; nx[cnt] = first[u]; first[u] = cnt; } int sig, root, size[maxn], pa[maxn], f[maxn], vis[maxn]; inline void findroot(int x, int fa) { size[x] = 1; f[x] = 0; for (int i = first[x]; i; i = nx[i]) { if ((to[i] == fa) || (vis[to[i]])) continue; findroot(to[i], x); size[x] += size[to[i]]; f[x] = max(f[x], size[to[i]]); } f[x] = max(f[x], sig - size[x]); if (f[x] < f[root]) root = x; } inline void build(int x) { vis[x] = 1; for (int i = first[x]; i; i = nx[i]) { if (vis[to[i]]) continue; root = 0; sig = size[to[i]]; findroot(to[i], x); pa[root] = x; build(root); } } namespace sp_lca { int size[maxn], dep[maxn], fa[maxn], bl[maxn], dp[maxn]; inline void dfs1(int x) { size[x] = 1; for (int i = first[x]; i; i = nx[i]) { if (to[i] == fa[x]) continue; fa[to[i]] = x; dep[to[i]] = dep[x] + 1; dp[to[i]] = dp[x] + val[i]; dfs1(to[i]); size[x] += size[to[i]]; } } inline void dfs2(int x, int col) { int k = 0; bl[x] = col; for (int i = first[x]; i; i = nx[i]) if (to[i] != fa[x] && size[to[i]] > size[k]) k = to[i]; if (!k) return; dfs2(k, col); for (int i = first[x]; i; i = nx[i]) if (to[i] != fa[x] && to[i] != k) dfs2(to[i], to[i]); } inline void init() { dfs1(1); dfs2(1, 1); } inline int lca(int x, int y) { while (bl[x] != bl[y]) { if (dep[bl[x]] < dep[bl[y]]) swap(x, y); x = fa[bl[x]]; } return dep[x] < dep[y] ? x : y; } } // namespace sp_lca inline int dis(int x, int y) { return sp_lca::dp[x] + sp_lca::dp[y] - (sp_lca::dp[sp_lca::lca(x, y)] << 1); } int rt[maxn], ls[maxn << 6], rs[maxn << 6], va[maxn << 6], ToT; inline void Insert(int &x, int l, int r, int pos, int v) { if (!x) x = ++ToT, va[x] = inf; va[x] = min(va[x], v); if (l == r) return; int mid = (l + r) >> 1; if (pos <= mid) Insert(ls[x], l, mid, pos, v); else Insert(rs[x], mid + 1, r, pos, v); } inline int query(int x, int l, int r, int L, int R) { if (!x) return inf; if (L <= l && r <= R) return va[x]; int mid = (l + r) >> 1, res = inf; if (L <= mid) res = min(res, query(ls[x], l, mid, L, R)); if (R > mid) res = min(res, query(rs[x], mid + 1, r, L, R)); return res; } int main() { // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); n = read(); rep(i, 2, n) { int u = read(), v = read(), w = read(); add(u, v, w); add(v, u, w); } f[0] = inf; root = 0; sig = n; findroot(1, 0); build(root); sp_lca ::init(); rep(i, 1, n) for (int x = i; x; x = pa[x]) Insert(rt[x], 1, n, i, dis(x, i)); // rep(i, 1, n) cout << pa[i] << endl; int q = read(); while (q--) { int u = read(), v = read(), x = read(); int cur = x, ans = inf; while (cur) { ans = min(ans, query(rt[cur], 1, n, u, v) + dis(cur, x)); cur = pa[cur]; } cout << ans << endl; } }