简单树

GitHub跳转原题关系图返回列表

点分治把树上距离按点分树 LCA 拆开,每个重心预处理管辖块的编号升序点表与距离前缀和,询问沿祖先链二分求区间距离和。

OJ: roj

题目 ID: 1763

难度:提高+/省选-

标签:点分治前缀和二分数据结构python

创建: 2026-10-07 23:00

更新: 2026-10-07 23:00

形式化题目

给出一棵 nn 个点的带权树 TT(边 (ai,bi)(a_i,b_i) 有长度 ci⩾0c_i \geqslant 0),点编号 1…n1 \dots n。 记 dist(u,v)\mathrm{dist}(u,v) 为树上两点间边权之和。顺次处理 mm 个操作,每个操作给定 L,R,xL,R,x,要求

S(L,R,x)=∑i=LRdist(i,x). S(L,R,x) = \sum_{i=L}^{R} \mathrm{dist}(i,x).

若 type=1type = 1 则数据强制在线:设 lastlast 为上一次操作的答案对 nn 取模的值(初始 last=0last = 0), 本次输入的三元组 (L′,R′,x′)(L',R',x') 需要按

L=L′⊕last,R=R′⊕last,x=x′⊕last L = L' \oplus last, \qquad R = R' \oplus last, \qquad x = x' \oplus last

解码后才能使用(⊕\oplus 为按位异或)。每个操作输出一行一个整数。

规模:1⩽n,m⩽600001 \leqslant n, m \leqslant 60000,0⩽type⩽10 \leqslant type \leqslant 1,0⩽c⩽1090 \leqslant c \leqslant 10^9。 答案上界约 n⋅n⋅109=3.6×1018n \cdot n \cdot 10^9 = 3.6 \times 10^{18},在 64 位整数范围内。

正解

思路

朴素做法与瓶颈。 先 O(n)O(n) 预处理出每点到根的距离与 LCA,就能 O(1)O(1) 算单点距离; 但一个询问要枚举 [L,R][L,R] 内的每个点,单次 O(n)O(n),总共 O(nm)=3.6×109O(nm) = 3.6 \times 10^9,必然超时。

常见的拆法是 dist(i,x)=disi+disx−2 dislca(i,x)\mathrm{dist}(i,x) = dis_i + dis_x - 2\,dis_{\mathrm{lca}(i,x)}: 前两项用 disdis 的前缀和 O(1)O(1) 得到,难的是 ∑i=LRdislca(i,x)\sum_{i=L}^{R} dis_{\mathrm{lca}(i,x)} ——它同时依赖 ii 的编号区间和 xx 的位置,两种信息不在同一维上。 本题的 std.cpp 走的是「树链剖分把根路径拆成 O(log⁡n)O(\log n) 段 + 可持久化线段树区间插入/查询」 (O((n+m)log⁡2n)O((n+m)\log^2 n));下面给出一条更短、常数更小的点分治路线,复杂度同为 O(log⁡2n)O(\log^2 n) 级别。

第一步:把距离拆到点分树上。 对树做点分治,得到点分树(重心树)。对任意两点 i,xi, x, 设 cc 是它们在点分树上的 LCA,则把 cc 摘掉之后 ii 与 xx 分属不同的连通块 (或其中之一就是 cc),所以树上 i→xi \to x 的路径必过 cc,于是

dist(i,x)=dist(i,c)+dist(c,x). \mathrm{dist}(i,x) = \mathrm{dist}(i,c) + \mathrm{dist}(c,x).

这一步把「树上两点距离」换成了「两个各自到同一个重心的距离之和」, 而 cc 只随 xx 变化——cc 恰好遍历 xx 在点分树上的祖先链,长度 O(log⁡n)O(\log n)。

第二步:按 cc 分组求和。 对 xx 的每个重心祖先 cc,满足 LCA(i,x)=c\mathrm{LCA}(i,x) = c 的 ii 组成的集合是「cc 管辖的连通块」减去「cc 通往 xx 的那个儿子的管辖块」。记

  • comp(u)comp(u):重心 uu 被摘除时它管辖的连通块;
  • bb:cc 在点分树上通往 xx 的儿子(c=xc = x 时不存在)。

则

S(L,R,x)=∑c∈anc(x)(∑i∈comp(c)∖comp(b)L⩽i⩽Rdist(i,c)⏟Ac+#{i∈comp(c)∖comp(b), L⩽i⩽R}⏟Nc⋅dist(c,x)), S(L,R,x) = \sum_{c \in anc(x)} \Big( \underbrace{\sum_{\substack{i \in comp(c) \setminus comp(b) \\ L \leqslant i \leqslant R}} \mathrm{dist}(i,c)}_{A_c} + \underbrace{\#\{ i \in comp(c) \setminus comp(b),\ L \leqslant i \leqslant R \}}_{N_c} \cdot \mathrm{dist}(c,x) \Big),

其中 c=xc = x 那一项取 comp(b)=∅comp(b) = \varnothing 且 dist(c,x)=0\mathrm{dist}(c,x) = 0,只剩 AcA_c。

第三步:把两个量做成「编号前缀」。 难点在于 Ac,NcA_c, N_c 都带一个编号区间 [L,R][L,R]。 把每个 comp(u)comp(u) 内的点按编号升序排成一个序列 p1<p2<⋯<ptp_1 < p_2 < \dots < p_t,并记

Nu(k)=#{j:pj⩽k},Gu(k)=∑j:pj⩽kdist(pj,u), N_u(k) = \#\{ j : p_j \leqslant k \}, \qquad G_u(k) = \sum_{j : p_j \leqslant k} \mathrm{dist}(p_j, u),

两者都随 kk 单调,于是 Nc=Nc(R)−Nc(L−1)N_c = N_c(R) - N_c(L-1)、Ac=Gc(R)−Gc(L−1)A_c = G_c(R) - G_c(L-1), 一次二分(upper_bound / bisect_right)就能在升序点表里定出位置,再读前缀和数组。

第四步:两套前缀和。 注意 AcA_c 里减掉的 comp(b)comp(b) 用的是到 cc 的距离, 不是到 bb 的距离,所以每个重心要维护两套数据:

数据 含义 用途
compNodes[c] / compPref[c] comp(c)comp(c) 的点按编号升序 + 到 cc 的距离前缀和 Nc(R)−Nc(L−1)N_c(R)-N_c(L-1)、Gc(R)−Gc(L−1)G_c(R)-G_c(L-1)
brNodes[b] / brPref[b] comp(b)comp(b) 的点按编号升序 + 到父重心 cc 的距离前缀和 从上一行里减掉的那部分

因为每个点出现在 O(log⁡n)O(\log n) 个 comp(⋅)comp(\cdot) 里,两套数据的总规模都是 O(nlog⁡n)O(n \log n)。

第五步:为什么不能离线。 直觉上「按 kk 排序 + 扫描」可以绕开二分, 但 type=1type = 1 时 (L,R,x)(L,R,x) 依赖上一次的答案,必须在线解码,无法重排询问顺序; 「编号升序 + 二分」正好是在线场景下的标准替代。

样例走一遍。 树为 1 ⁣− ⁣2(3)1\!-\!2(3)、1 ⁣− ⁣3(3)1\!-\!3(3)、2 ⁣− ⁣4(3)2\!-\!4(3)、2 ⁣− ⁣5(3)2\!-\!5(3)。 点数 55,摘掉 22 后最大块只有 33,故根重心是 22;它的分支是 {1,3}\{1,3\}、{4}\{4\}、{5}\{5\}, {1,3}\{1,3\} 的重心是 11,再往下 {3}\{3\} 的重心是 33。于是

vv anc(v)anc(v)(重心, 到它的距离) comp(v)comp(v)
1 (2,3), (1,0)(2,3),\ (1,0) {1,3}\{1,3\}
2 (2,0)(2,0) {1,2,3,4,5}\{1,2,3,4,5\}
3 (2,6), (1,3), (3,0)(2,6),\ (1,3),\ (3,0) {3}\{3\}
4 (2,3), (4,0)(2,3),\ (4,0) {4}\{4\}
5 (2,3), (5,0)(2,3),\ (5,0) {5}\{5\}

问 (L,R,x)=(1,5,3)(L,R,x) = (1,5,3) 时,沿 anc(3)anc(3) 逐层累加:

cc bb comp(c)∖comp(b)comp(c) \setminus comp(b) 落在 [1,5][1,5] 的点数 该部分的 ∑dist(i,c)\sum \mathrm{dist}(i,c) dist(c,3)\mathrm{dist}(c,3) 本层贡献
2 1 5−2=35 - 2 = 3 15−9=615 - 9 = 6 6 6+3×6=246 + 3 \times 6 = 24
1 3 2−1=12 - 1 = 1 3−3=03 - 3 = 0 3 0+1×3=30 + 1 \times 3 = 3
3 — 1(只有点 3 自己) 0 0 0

合计 2727,与题面样例一致。第二、三个询问同理得 1515、1212。

代码

Python 版:

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 迭代实现点分治,避免链形数据深度 6×1046 \times 10^4 时爆栈):

cpp
/**
 * 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,块大小按层求和为 O(nlog⁡n)O(n \log n),故预处理为 O(nlog⁡n)O(n \log n);每个询问沿 xx 的 O(log⁡n)O(\log n) 个重心祖先各做 44 次二分, 单次 O(log⁡2n)O(\log^2 n)。总计 O(nlog⁡n+mlog⁡2n)O(n \log n + m \log^2 n), 与 std.cpp 的树链剖分 + 可持久化线段树同阶(那套是 O((n+m)log⁡2n)O((n+m)\log^2 n))。
  • 空间:每个点被登记进 O(log⁡n)O(\log n) 个 comp(⋅)comp(\cdot),两套前缀和各 O(nlog⁡n)O(n \log n); C++ 用 int/long long 各存一份,n=60000n = 60000 时约 10610^6 量级条目,几十 MB。 实测(随仓 10 个测试点,限时 5000 ms / 512 MB):C++ 最慢点是 n=m=60000n = m = 60000 的链, 105 ms、峰值 48 MB;Python 最慢点是 n=m=60000n = m = 60000 的完全二叉树,1.23 s,均在限内。 两语言在 10 个点上输出逐字节一致,另与暴力 dist 矩阵做了 255 组随机对拍(含 n=1n=1、 边权 00 与 10910^9、type=0/1)全部一致。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一算法、同一套公式, 只是 C++ 用链式前向星 + upper_bound,Python 用邻接表 + bisect_right。 Python 侧的常数更大(建表与询问循环都是解释执行),但算法未降级, 即使个别极限点超时也属于语言常数问题。

总结

  • 换个「LCA」定义就能拆距离:树上距离公式 dist(i,x)=disi+disx−2dislca\mathrm{dist}(i,x)=dis_i+dis_x-2dis_{\mathrm{lca}} 里的 lca\mathrm{lca} 需要在线求;改成点分树上的 LCA,距离直接裂成 dist(i,c)+dist(c,x)\mathrm{dist}(i,c)+\mathrm{dist}(c,x),cc 只有 O(log⁡n)O(\log n) 个候选。
  • 编号区间 + 树上位置 = 升序点表 + 前缀和:把「comp(u)comp(u) 内编号 ⩽k\leqslant k」做成 有序序列上的二分,是处理「编号是一维、树是另一维」这类询问的通用手法。
  • 减掉的部分要用对参照物:comp(b)comp(b) 要从 comp(c)comp(c) 里减掉,但距离必须都算到 cc, 所以每个重心维护两套前缀和——这是本题最容易写错的一步。
  • 强制在线只是「不能重排询问」:它并不禁止 O(nlog⁡n)O(n \log n) 的预处理, 也不禁止二分;真正被禁掉的只有「把所有询问按 kk 排序后扫描」这类离线技巧。
  • 本题素材源里带数据生成脚本 data.py,说明测试数据是自造的(并非官方原始数据), 题面也可能来自网络重建;因此「出题意图」与官方原题可能存在偏差。 题面【提示】里的操作编号也明显错位(把第 2 次操作写成「第 3 次」、第 3 次写成「第 4 次」), 但样例输入/输出本身自洽,上面已逐项复核。
  • 素材源的 std.cpp(树链剖分 + 可持久化线段树,O((n+m)log⁡2n)O((n+m)\log^2 n))已编译实跑, 10 个测试点与 .out 全部一致,题面与数据自洽;本文只是换了一条更短的点分治路线, 两套做法的复杂度同阶。