点分治把树上距离按点分树 LCA 拆开,每个重心预处理管辖块的编号升序点表与距离前缀和,询问沿祖先链二分求区间距离和。
OJ: roj
题目 ID: 1763
难度:提高+/省选-
标签:点分治前缀和二分数据结构python
创建: 2026-10-07 23:00
更新: 2026-10-07 23:00
形式化题目
给出一棵
若
解码后才能使用(
规模:
正解
思路
朴素做法与瓶颈。 先
常见的拆法是 std.cpp 走的是「树链剖分把根路径拆成
第一步:把距离拆到点分树上。 对树做点分治,得到点分树(重心树)。对任意两点
这一步把「树上两点距离」换成了「两个各自到同一个重心的距离之和」,
而
第二步:按
:重心 被摘除时它管辖的连通块; : 在点分树上通往 的儿子( 时不存在)。
则
其中
第三步:把两个量做成「编号前缀」。 难点在于
两者都随 upper_bound / bisect_right)就能在升序点表里定出位置,再读前缀和数组。
第四步:两套前缀和。 注意
| 数据 | 含义 | 用途 |
|---|---|---|
compNodes[c] / compPref[c] |
||
brNodes[b] / brPref[b] |
从上一行里减掉的那部分 |
因为每个点出现在
第五步:为什么不能离线。 直觉上「按
样例走一遍。 树为
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 |
问
| 该部分的 |
本层贡献 | ||||
|---|---|---|---|---|---|
| 2 | 1 | 6 | |||
| 1 | 3 | 3 | |||
| 3 | — | 1(只有点 3 自己) | 0 | 0 | 0 |
合计
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 23:00
# update_at: 2026-10-07 23:00
import sys
from bisect import bisect_right
from itertools import accumulate
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Neigh = list[list[tuple[int, int]]] # 邻接表:点 -> [(邻居, 边权)]
type Chain = list[tuple[int, int]] # 点分树祖先链:[(祖先重心, 到它的距离)],根在前、自己最后
type NodeList = list[list[int]] # 每个重心管辖块内的点,按编号升序
type PrefList = list[list[int]] # 对应的「距离」前缀和,首项为 0
type Block = tuple[NodeList, PrefList] # 一个重心的「点表 + 距离前缀和」
def decompose(n: int, adj: Neigh) -> tuple[list[Chain], Block, Block]:
"""点分治(迭代):返回每个点的祖先链,以及每个重心的两种「点表 + 距离前缀和」。
comp 侧:重心 c 管辖连通块内的点到 c 的距离;
br 侧:重心 c 管辖连通块内的点到「c 在点分树上的父亲」的距离。
每个点被登记进祖先链的顺序就是重心被摘除的顺序,因此链天然是根在前、自己在最后。
"""
removed = [False] * (n + 1)
chains: list[Chain] = [[] for _ in range(n + 1)]
comp_nodes: NodeList = [[] for _ in range(n + 1)]
comp_prefs: PrefList = [[] for _ in range(n + 1)]
br_nodes: NodeList = [[] for _ in range(n + 1)]
br_prefs: PrefList = [[] for _ in range(n + 1)]
pending: list[tuple[list[int], list[int]] | None] = [None] * (n + 1) # 分支代表 -> 待转交的 br 侧数据
par = [0] * (n + 1) # 上一次 BFS 的父指针(各步复用)
size = [0] * (n + 1) # 连通块内以 start 为根时的子树大小
dist = [0] * (n + 1) # 到当前重心的距离
branch = [0] * (n + 1) # 点属于重心的哪个邻居分支(分支代表 = 那个邻居)
stack = [1]
while stack:
start = stack.pop()
# 1) BFS 收集本连通块,并得到以 start 为根的父子关系
# (边遍历边扩容:Python 的 list 迭代会看到新追加的元素)
order = [start]
par[start] = 0
for u in order:
pu = par[u]
for v, _w in adj[u]:
if v != pu and not removed[v]:
par[v] = u
order.append(v)
total = len(order)
# 2) 逆 BFS 序求子树大小
for u in reversed(order):
s = 1
pu = par[u]
for v, _w in adj[u]:
if v != pu and not removed[v]:
s += size[v]
size[u] = s
# 3) 从 start 沿「大小 > total/2」的重儿子往下走,落点就是重心
c = start
while True:
heavy = 0
pc = par[c]
for v, _w in adj[c]:
if v != pc and not removed[v] and size[v] * 2 > total:
heavy = v
break
if not heavy:
break
c = heavy
# 4) 本块是上一层某分支时,父重心侧的 br 数据挂在分支代表 start 上,转交给本块重心 c
if start != c and pending[start] is not None:
pending[c] = pending[start]
pending[start] = None
# 5) 从重心 c 出发 BFS:求块内各点到 c 的距离,并记下它属于哪个邻居分支
order = [c]
par[c] = 0
dist[c] = 0
for u in order:
du = dist[u]
for v, w in adj[u]:
if v != par[u] and not removed[v]:
par[v] = u
dist[v] = du + w
branch[v] = v if u == c else branch[u]
order.append(v)
# 6) 每个分支的点按编号升序排好,配一份「到父重心 c」的距离前缀和,挂在分支代表上
groups: dict[int, list[int]] = {}
for v in order:
if v != c:
groups.setdefault(branch[v], []).append(v)
for rep, members in groups.items():
members.sort()
pending[rep] = (members, list(accumulate((dist[v] for v in members), initial=0)))
# 7) 登记本重心:升序点表 + 到 c 的距离前缀和 + 块内每点的祖先链
order.sort()
comp_nodes[c] = order
comp_prefs[c] = list(accumulate((dist[v] for v in order), initial=0))
for v in order:
chains[v].append((c, dist[v]))
# 8) 摘掉重心,各分支(即 c 的未摘邻居)成为独立子问题
removed[c] = True
stack.extend(groups)
for c in range(1, n + 1): # 转交完成后才认领:每个非根重心都有一份 br 侧数据
if pending[c] is not None:
br_nodes[c], br_prefs[c] = pending[c]
return chains, (comp_nodes, comp_prefs), (br_nodes, br_prefs)
def range_dist(chain: Chain, L: int, R: int, comp: Block, br: Block) -> int:
"""求 Σ_{i∈[L,R]} dist(i,x),x 的祖先链是 chain。
记 c 为 i、x 在点分树上的 LCA,则 c 落在树上 i→x 的路径上,dist(i,x) = dist(i,c) + dist(c,x)。
按 c 分组累加:c 恰好遍历 chain,且「LCA(i,x) = c」的点集是 comp(c) \\ comp(b),
b 是 c 在点分树上通往 x 的儿子;点集按编号升序,所以交 [L,R] 的点数与距离和都是一次二分。
"""
comp_nodes, comp_prefs = comp
br_nodes, br_prefs = br
lo = L - 1
tot = 0
for j in range(len(chain) - 1):
c, d = chain[j] # c = LCA 这一层的重心,d = dist(c,x)
b = chain[j + 1][0] # b = c 通往 x 的儿子,它的块就是「要减掉的那部分」
cn, cp = comp_nodes[c], comp_prefs[c]
bn, bp = br_nodes[b], br_prefs[b]
n_hi, n_lo = bisect_right(cn, R), bisect_right(cn, lo)
m_hi, m_lo = bisect_right(bn, R), bisect_right(bn, lo)
cnt = (n_hi - n_lo) - (m_hi - m_lo) # comp(c) \\ comp(b) 里落在 [L,R] 的点数
tot += (cp[n_hi] - cp[n_lo]) - (bp[m_hi] - bp[m_lo]) + cnt * d
cn, cp = comp_nodes[chain[-1][0]], comp_prefs[chain[-1][0]] # c = x 这一层:分支为空,d = 0
return tot + cp[bisect_right(cn, R)] - cp[bisect_right(cn, lo)]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, online = next(data), next(data), next(data)
adj: Neigh = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b, c = next(data), next(data), next(data)
adj[a].append((b, c))
adj[b].append((a, c))
chains, comp, br = decompose(n, adj)
out: list[str] = []
last = 0 # 强制在线时的 lastans = 上一次答案 mod n,初值 0
for _ in range(m):
L, R, x = next(data), next(data), next(data)
if online:
L ^= last
R ^= last
x ^= last
ans = range_dist(chains[x], L, R, comp, br)
out.append(str(ans))
last = ans % n
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法,用显式栈 + BFS 迭代实现点分治,避免链形数据深度
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 23:00
* update_at: 2026-10-07 23:00
*/
// main.cpp:一本通 1763《简单树》。带权树上的「编号区间到定点距离和」询问,可强制在线。
//
// 与 main.py 同一算法:点分治 + 前缀和 + 二分。
// 记 c 为 i、x 在点分树上的 LCA,此时 c 一定落在树上 i→x 的路径上,于是
// dist(i,x) = dist(i,c) + dist(c,x)。
// 把 i 按 c = LCA(i,x) 分组(c 恰好遍历 x 的点分树祖先链),
// Σ_{i∈[L,R]} dist(i,x) = Σ_c [ Σ_{i∈[L,R], LCA=c} dist(i,c)
// + #{i∈[L,R], LCA=c} * dist(c,x) ],
// 其中「LCA(i,x) = c」的 i 集合 = comp(c) \ comp(b),b 是 c 在点分树上通往 x 的儿子。
// 对每个重心 c 预处理:
// compNodes[c] / compPref[c] —— 其管辖连通块内的点按编号升序 + 到 c 的距离前缀和;
// brNodes[b] / brPref[b] —— b 管辖的连通块内的点按编号升序 + 到「父重心」的距离前缀和。
// 两者都用编号升序排列,故 #{i ≤ k, i∈S} 与对应的距离和都是一次二分 + 前缀和。
// 复杂度:预处理 O(n log n),单次询问 O(log^2 n)(沿祖先链 O(log n) 次二分),空间 O(n log n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 60005;
int n, m, typeFlag;
// 邻接表(链式前向星)
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], ecnt;
ll wt[MAXN << 1];
bool removed[MAXN]; // 点分治中已被摘掉的重心
int sz[MAXN]; // 连通块内以 start 为根时的子树大小
int par[MAXN]; // 上面那次 BFS 的父指针(多次复用)
ll distc[MAXN]; // 到当前重心的距离
int order[MAXN]; // BFS 序缓冲
vector<int> ancC[MAXN]; // ancC[v]:v 的点分树祖先链(根在前,末尾是 v 自己)
vector<ll> ancD[MAXN]; // ancD[v][j] = dist(ancC[v][j], v)
vector<int> compNodes[MAXN]; // 重心 c 管辖连通块内的点,按编号升序
vector<ll> compPref[MAXN]; // 对应的「到 c 的距离」前缀和,compPref[c][0] = 0
vector<int> brNodes[MAXN]; // 重心 b 管辖连通块内的点,按编号升序
vector<ll> brPref[MAXN]; // 对应的「到 b 的父重心」的距离前缀和
void addEdge(int a, int b, ll c) {
to[++ecnt] = b; wt[ecnt] = c; nxt[ecnt] = head[a]; head[a] = ecnt;
}
// 点分治:迭代实现(显式栈 + BFS),避免链形数据深度 6e4 时爆栈。
// 顺带把每个重心管辖块的「编号升序点表 + 距离前缀和」建好,
// 并把 (重心, 距离) 追加到块内每个点的祖先链上(父重心先于子重心处理,故链天然根在前)。
void decompose() {
vector<int> stk;
stk.push_back(1);
while (!stk.empty()) {
int start = stk.back();
stk.pop_back();
// 1) BFS 收集连通块,并得到以 start 为根的父子关系
int qt = 0;
order[qt++] = start;
par[start] = 0;
for (int qi = 0; qi < qt; ++qi) {
int u = order[qi];
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (v != par[u] && !removed[v]) { par[v] = u; order[qt++] = v; }
}
}
int total = qt;
// 2) 逆 BFS 序求子树大小
for (int i = total - 1; i >= 0; --i) {
int u = order[i];
sz[u] = 1;
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (v != par[u] && !removed[v]) sz[u] += sz[v];
}
}
// 3) 从 start 沿「大小 > total/2 的重儿子」往下走,落到重心
int c = start;
for (;;) {
int go = 0;
for (int e = head[c]; e; e = nxt[e]) {
int v = to[e];
if (v != par[c] && !removed[v] && sz[v] * 2 > total) { go = v; break; }
}
if (!go) break;
c = go;
}
// 3.5) 本块是上一层的某个分支,父重心侧的「到父重心距离前缀和」挂在分支代表 start 上,
// 现在本块的重心 c 才是点分树上这一层的节点,把它转交给 c。
if (start != c) {
brNodes[c].swap(brNodes[start]);
brPref[c].swap(brPref[start]);
}
// 4) 从重心 c 出发 BFS,求块内各点到 c 的距离
qt = 0;
order[qt++] = c;
par[c] = 0;
distc[c] = 0;
for (int qi = 0; qi < qt; ++qi) {
int u = order[qi];
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (v != par[u] && !removed[v]) {
par[v] = u;
distc[v] = distc[u] + wt[e];
order[qt++] = v;
}
}
}
total = qt;
// 5) 登记祖先链 + 该重心管辖块的「编号升序点表 / 距离前缀和」
compNodes[c].reserve(total);
compPref[c].reserve(total + 1);
compPref[c].push_back(0);
for (int i = 0; i < total; ++i) compNodes[c].push_back(order[i]);
sort(compNodes[c].begin(), compNodes[c].end());
for (int i = 0; i < total; ++i) {
int v = compNodes[c][i];
ancC[v].push_back(c);
ancD[v].push_back(distc[v]);
compPref[c].push_back(compPref[c].back() + distc[v]);
}
// 6) 摘掉重心,各分支成为独立的子问题;分支代表就是 c 的未摘邻居
removed[c] = true;
for (int e = head[c]; e; e = nxt[e]) {
int v = to[e];
if (!removed[v]) {
stk.push_back(v);
// 该分支内的点到「父重心 c」的距离前缀和(分支重心稍后才知道是谁,
// 这里先挂在分支代表 v 上,等该分支处理时再转交给它的重心)
int bt = 0;
order[bt++] = v;
par[v] = c;
distc[v] = wt[e];
for (int qi = 0; qi < bt; ++qi) {
int u = order[qi];
for (int f = head[u]; f; f = nxt[f]) {
int w = to[f];
if (w != par[u] && !removed[w]) {
par[w] = u;
distc[w] = distc[u] + wt[f];
order[bt++] = w;
}
}
}
vector<int> &bn = brNodes[v];
bn.assign(order, order + bt);
sort(bn.begin(), bn.end());
vector<ll> &bp = brPref[v];
bp.assign(bt + 1, 0);
for (int i = 0; i < bt; ++i) bp[i + 1] = bp[i] + distc[bn[i]];
}
}
}
}
// Σ_{i=L..R} dist(i,x):沿 x 的点分树祖先链累加「按 LCA 分组」的两项贡献。
ll queryRange(int L, int R, int x) {
const vector<int> &cs = ancC[x];
const vector<ll> &ds = ancD[x];
int len = (int)cs.size();
ll tot = 0;
for (int j = 0; j + 1 < len; ++j) {
int c = cs[j], b = cs[j + 1];
const vector<int> &cn = compNodes[c];
const vector<ll> &cp = compPref[c];
const vector<int> &bn = brNodes[b];
const vector<ll> &bp = brPref[b];
// 编号 ≤ k 的点数(即 [1,k] 与集合的交集大小)
int nR = (int)(upper_bound(cn.begin(), cn.end(), R) - cn.begin());
int nL = (int)(upper_bound(cn.begin(), cn.end(), L - 1) - cn.begin());
int mR = (int)(upper_bound(bn.begin(), bn.end(), R) - bn.begin());
int mL = (int)(upper_bound(bn.begin(), bn.end(), L - 1) - bn.begin());
// (comp(c) \ comp(b)) ∩ [L,R] 内的「到 c 的距离和」+ 「点数 * dist(c,x)」
tot += (cp[nR] - cp[nL]) - (bp[mR] - bp[mL]) + (ll)((nR - nL) - (mR - mL)) * ds[j];
}
int c = cs[len - 1]; // c == x 这一层:分支为空,dist(c,x) = 0,只剩距离和
const vector<int> &cn = compNodes[c];
const vector<ll> &cp = compPref[c];
int nR = (int)(upper_bound(cn.begin(), cn.end(), R) - cn.begin());
int nL = (int)(upper_bound(cn.begin(), cn.end(), L - 1) - cn.begin());
tot += cp[nR] - cp[nL];
return tot;
}
int main() {
if (scanf("%d %d %d", &n, &m, &typeFlag) != 3) return 0;
for (int i = 1; i < n; ++i) {
int a, b;
ll c;
scanf("%d %d %lld", &a, &b, &c);
addEdge(a, b, c);
addEdge(b, a, c);
}
decompose();
ll last = 0;
for (int i = 0; i < m; ++i) {
ll L, R, X;
scanf("%lld %lld %lld", &L, &R, &X);
if (typeFlag) { L ^= last; R ^= last; X ^= last; }
ll ans = queryRange((int)L, (int)R, (int)X);
printf("%lld\n", ans);
last = ans % n;
}
return 0;
}复杂度
- 时间:点分治每层对每个块做常数次 BFS,块大小按层求和为
,故预处理为 ;每个询问沿 的 个重心祖先各做 次二分, 单次 。总计 , 与 std.cpp的树链剖分 + 可持久化线段树同阶(那套是)。 - 空间:每个点被登记进
个 ,两套前缀和各 ; C++ 用 int/long long各存一份,时约 量级条目,几十 MB。 实测(随仓 10 个测试点,限时 5000 ms / 512 MB):C++ 最慢点是 的链, 105 ms、峰值 48 MB;Python 最慢点是 的完全二叉树,1.23 s,均在限内。 两语言在 10 个点上输出逐字节一致,另与暴力 dist矩阵做了 255 组随机对拍(含、 边权 与 、 type=0/1)全部一致。 - 与 C++ 解法的关系:
main.cpp与main.py是同一算法、同一套公式, 只是 C++ 用链式前向星 +upper_bound,Python 用邻接表 +bisect_right。 Python 侧的常数更大(建表与询问循环都是解释执行),但算法未降级, 即使个别极限点超时也属于语言常数问题。
总结
- 换个「LCA」定义就能拆距离:树上距离公式
里的 需要在线求;改成点分树上的 LCA,距离直接裂成 , 只有 个候选。 - 编号区间 + 树上位置 = 升序点表 + 前缀和:把「
内编号 」做成 有序序列上的二分,是处理「编号是一维、树是另一维」这类询问的通用手法。 - 减掉的部分要用对参照物:
要从 里减掉,但距离必须都算到 , 所以每个重心维护两套前缀和——这是本题最容易写错的一步。 - 强制在线只是「不能重排询问」:它并不禁止
的预处理, 也不禁止二分;真正被禁掉的只有「把所有询问按 排序后扫描」这类离线技巧。 - 本题素材源里带数据生成脚本
data.py,说明测试数据是自造的(并非官方原始数据), 题面也可能来自网络重建;因此「出题意图」与官方原题可能存在偏差。 题面【提示】里的操作编号也明显错位(把第 2 次操作写成「第 3 次」、第 3 次写成「第 4 次」), 但样例输入/输出本身自洽,上面已逐项复核。 - 素材源的
std.cpp(树链剖分 + 可持久化线段树,)已编译实跑, 10 个测试点与 .out全部一致,题面与数据自洽;本文只是换了一条更短的点分治路线, 两套做法的复杂度同阶。