用斐波那契加法公式把按深度加 Fib(k+D) 拆成两个静态系数,子树区间差分套树状数组,路径和转为根前缀和与 LCA。
OJ: roj
题目 ID: 1765
难度:提高+/省选-
标签:数学斐波那契树状数组差分LCA倍增python
创建: 2026-10-08 00:32
更新: 2026-10-08 00:32
形式化题目
给定一棵以
U X k:对子树内每个节点 (含 自己),设 到 的边数为 , 令 ; Q X Y:求到 的唯一简单路径上所有节点(含端点)的权值和,模 输出。
其中
暴力解法
思路
按题面直译即可。每个点存一个权值数组 val[1..n]。
- 修改:从
出发 DFS 整棵子树,向下传一个距离 ,把 加到 val[v]。 由于到子树内任一点 的路径必过 ,只用深度差就能得到 , 不需要真的记路径。 - 询问:先把
、 提到同一深度,再一起往上跳,途中把经过的点权加起来, 跳到同一个点后它是唯一被重复计数的点,减掉一次即可。
Fib 的项要现算:
代码
复杂度
单次修改
瓶颈
表面看瓶颈是"子树/路径要逐个点跑",但真正的障碍在修改的那一项:
对同一次修改而言,系数
正解
思路
关键观察:斐波那契加法公式把"变化的加数"变成"两个固定序列的线性组合"。 Fibonacci 有恒等式(对全体整数都成立)
取
观察重点在于:
第二步:把"各类更新的加权和"沉淀成每个点上的三个累计量。
对每个点
"子树是 DFS 先序中的连续区间"这一性质让
第三步:询问不需要真的爬路径。 记
最后一步化归:
Fib 系数怎么算。
| 符号 | 含义 | 何时算 |
|---|---|---|
| 根的深度取 |
预处理 | |
| 点 |
预处理(线性递推到 |
|
| 根到 |
预处理 | |
| 单次更新的特征量 | 每次 U |
|
| 单次更新的两个系数 | 每次 U(倍增) |
|
| 差分的第三维修正值 | 每次 U |
|
| 覆盖当前点的更新的三类累加和 | 差分树状数组查询 |
代码
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-08 00:32
# update_at: 2026-10-08 00:32
import sys
from collections.abc import Iterator
MOD = 10 ** 9 + 7
LOG = 17 # 1e5 的二进制位数,倍增 LCA 的层数
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type UpTable = list[list[int]] # up[j][v] = v 的第 2^j 级祖先,0 表示不存在
type GroupBit = list[list[int]] # 三元差分树状数组 bit[pos] = [Σc0, Σc1, Σd]
type Trio = tuple[int, int, int] # 某位置上的三个累计量 (Σc0, Σc1, Σd)
type Children = list[list[int]] # child[u] = u 的孩子列表
type FibPair = tuple[int, int] # 成对返回的斐波那契量:(Fib(t), Fib(t+1)) 或 (c0, c1)
type TreeInfo = tuple[list[int], list[int], list[int], list[int], list[int], list[int],
list[int], UpTable] # 八元组,各分量含义见下一行注释
# TreeInfo = (fa, tin, sz, dep, pa, pb, fib_small, up):父亲 / 先序编号 / 子树大小 / 深度 /
# 根到各点的 ΣFib(dep)、ΣFib(dep+1) / Fib(0..n+1) / 倍增祖先表,
# 全部只依赖树的静态形状,建好之后不再改变
def fib_pair(t: int) -> FibPair:
"""返回 (Fib(t), Fib(t+1)) mod MOD,要求 t >= 0,倍增法 O(log t)。"""
if t == 0:
return 0, 1
a, b = fib_pair(t >> 1)
even = a * (2 * b - a) % MOD # Fib(2i) = Fib(i)*(2Fib(i+1)-Fib(i))
odd = (a * a + b * b) % MOD # Fib(2i+1) = Fib(i)^2 + Fib(i+1)^2
return (odd, (even + odd) % MOD) if t & 1 else (even, odd)
def fib_coef(big: int) -> FibPair:
"""更新系数 (Fib(big-1), Fib(big)) mod MOD。
big = k - dep[X] 可能为负,用 Fib(-p) = (-1)^(p+1)*Fib(p) 延拓:
此时两个系数正好是 ±Fib(p+1) 与 ±Fib(p),符号由 p 的奇偶决定。
"""
positive = abs(big)
f, g = fib_pair(positive) # Fib(p), Fib(p+1)
if big >= 0:
return (g - f) % MOD, f # Fib(K-1) = Fib(K+1) - Fib(K)
sign = 1 if positive & 1 else -1 # (-1)^(p+1)
return (-sign * g) % MOD, (sign * f) % MOD
def build_static(n: int, fa: list[int], child: Children) -> TreeInfo:
"""预处理所有只与树形状有关的量:先序编号、子树大小、深度、Fib 前缀和、倍增表。
先序编号让"子树"变成一段连续区间,这是后面差分树状数组能用起来的前提:
一次更新只在这段区间的左右端点各记一笔,某点被多少更新覆盖就看它的前缀和。
"""
tin = [0] * (n + 1)
dep = [0] * (n + 1)
order: list[int] = []
stack = [1]
while stack:
u = stack.pop()
tin[u] = len(order) + 1
order.append(u)
for v in child[u]:
dep[v] = dep[u] + 1
stack.append(v)
sz = [1] * (n + 1) # 子树大小:逆先序把大小并给父亲
for u in reversed(order):
if u != 1:
sz[fa[u]] += sz[u]
# fib_small[t] = Fib(t) mod MOD;深度只用到 0..n,多留一格给 Fib(dep+1)
fib_small = [0] * (n + 2)
fib_small[1] = 1
for t in range(2, n + 2):
fib_small[t] = (fib_small[t - 1] + fib_small[t - 2]) % MOD
# pa / pb:根到 u 路径上 ΣFib(dep[v]) 与 ΣFib(dep[v]+1),是本题两条静态权序列的前缀和
pa = [0] * (n + 1)
pb = [0] * (n + 1)
for u in order:
pa[u] = (pa[fa[u]] + fib_small[dep[u]]) % MOD
pb[u] = (pb[fa[u]] + fib_small[dep[u] + 1]) % MOD
# 倍增表:up[0] = fa,up[j] 由 up[j-1] 复合而来
up: UpTable = [fa[:]]
for _ in range(1, LOG):
prev = up[-1]
up.append([prev[prev[v]] for v in range(n + 1)])
return fa, tin, sz, dep, pa, pb, fib_small, up
def bit_add(pos: int, delta: Trio, bit: GroupBit, n: int) -> None:
"""区间差分的左端点写法:从 pos 起往上累加 delta,右端点记 -delta 即自动抵消。
不做取模:单点最多累积 m 次 MOD 级增量(1e6 × 1e9),Python 大整数完全安全,
查询时统一取模更快。三个分量共用一个下标,所以放在同一层 while 里一起维护。
"""
while pos <= n:
slot = bit[pos]
slot[0] += delta[0]
slot[1] += delta[1]
slot[2] += delta[2]
pos += pos & -pos
def bit_sum(pos: int, bit: GroupBit) -> Trio:
"""位置 pos 的三元前缀和:所有子树区间覆盖了 pos 的更新累积出的 (Σc0, Σc1, Σd)。"""
s0 = s1 = s2 = 0
while pos > 0:
slot = bit[pos]
s0 += slot[0]
s1 += slot[1]
s2 += slot[2]
pos -= pos & -pos
return s0 % MOD, s1 % MOD, s2 % MOD
def lca(a: int, b: int, dep: list[int], fa: list[int], up: UpTable) -> int:
"""求 a、b 的最近公共祖先:先拉到同一深度,再同步上跳到分叉点的儿子。"""
if dep[a] < dep[b]:
a, b = b, a
diff = dep[a] - dep[b]
for j in range(LOG):
if diff >> j & 1:
a = up[j][a]
if a == b:
return a
for j in range(LOG - 1, -1, -1):
if up[j][a] != up[j][b]:
a, b = up[j][a], up[j][b]
return fa[a]
def handle_ops(tokens: Iterator[bytes], m: int, n: int, tree: TreeInfo) -> list[str]:
"""按输入顺序处理 m 个操作,返回每个询问的答案(按询问顺序)。"""
fa, tin, sz, dep, pa, pb, fib_small, up = tree
bit: GroupBit = [[0, 0, 0] for _ in range(n + 1)]
out: list[str] = []
for _ in range(m):
op = next(tokens)
if op == b'U':
x, k = int(next(tokens)), int(next(tokens))
c0, c1 = fib_coef(k - dep[x]) # Fib(K-1), Fib(K),K = k - dep[x]
# 差分的第三维修正项 d:把"根到 X 之上那半段"的 Fib 前缀和从 T[u] 里减掉
d = (c0 * pa[fa[x]] + c1 * pb[fa[x]]) % MOD
head = tin[x] # 子树区间 [head, head+sz-1]
tail = head + sz[x] # 差分右端点;等于 n+1 时不会被任何前缀和查到,省掉
bit_add(head, (c0, c1, d), bit, n)
if tail <= n:
bit_add(tail, (-c0, -c1, -d), bit, n)
else:
x, y = int(next(tokens)), int(next(tokens))
l = lca(x, y, dep, fa, up)
sx, sy, sl = bit_sum(tin[x], bit), bit_sum(tin[y], bit), bit_sum(tin[l], bit)
# T[u] = 根到 u 的点权和 = Σc0·PA[u] + Σc1·PB[u] - Σd,静态前缀和乘上累计量即可
tx = (pa[x] * sx[0] + pb[x] * sx[1] - sx[2]) % MOD
ty = (pa[y] * sy[0] + pb[y] * sy[1] - sy[2]) % MOD
tl = (pa[l] * sl[0] + pb[l] * sl[1] - sl[2]) % MOD
# 点 L 在两条根链里各算了一次,把它换成点权公式(比 T[L] 只少一个 Σd 项)
value_l = (fib_small[dep[l]] * sl[0] + fib_small[dep[l] + 1] * sl[1]) % MOD
out.append(str((tx + ty - 2 * tl + value_l) % MOD))
return out
def solve() -> None:
tokens = iter(sys.stdin.buffer.read().split())
n, m = int(next(tokens)), int(next(tokens))
fa = [0] * (n + 1) # 父亲,根的父亲是 0 号哨兵(它的 Fibonacci 前缀和都是 0)
child: Children = [[] for _ in range(n + 1)]
for v in range(2, n + 1):
fa[v] = int(next(tokens))
child[fa[v]].append(v)
tree = build_static(n, fa, child)
out = handle_ops(tokens, m, n, tree)
sys.stdout.write('\n'.join(out) + ('\n' if out else ''))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-08 00:32
* update_at: 2026-10-08 00:32
*/
// ROJ 1765《树上斐波那契》
// ---------------------------------------------------------------------------
// 数学依据(Fibonacci 加法公式,对全体整数成立):
// Fib(a+b) = Fib(a)*Fib(b+1) + Fib(a-1)*Fib(b),
// 负数下标按 Fib(-n) = (-1)^(n+1)*Fib(n) 延拓,于是 Fib(0)=0、Fib(-1)=1。
//
// 关键转化:更新 U X k 对 X 子树内的点 v 加上
// Fib(k + dep[v] - dep[X]) = c1*Fib(dep[v]+1) + c0*Fib(dep[v]), c1=Fib(K), c0=Fib(K-1),
// K = k - dep[X](根的深度取 0,D = dep[v] - dep[X])。
// 系数 c0,c1 只与操作有关;Fib(dep[v])、Fib(dep[v]+1) 只与节点的静态深度有关。
//
// 做法(Fib 前缀和 + 子树差分树状数组 + 倍增 LCA):
// 记 val[v] 为点权,T[u] = Σ_{v 在根..u 的路径上} val[v](根到 u 的链和),
// 则路径和 = T[X] + T[Y] - 2*T[L] + val[L](L 为 X,Y 的 LCA)。
// 记 pa[w] = Σ_{v 在根..w 上} Fib(dep[v])、pb 同理换成 Fib(dep[v]+1)。
// 一次更新对 T[u] 的贡献只在 u ∈ X 子树时非零,此时根到 u 上的 Fib 前缀和
// 比根到 x 的父亲那段多出的部分恰好是 pa[u]-pa[faX] 与 pb[u]-pb[faX],于是
// T[u] = pa[u]*S0[u] + pb[u]*S1[u] - SD[u]
// 其中 S0[u]=Σc0、S1[u]=Σc1、SD[u]=Σ(c0*pa[faX]+c1*pb[faX]),
// 三个求和都只对"子树区间包含 tin[u] 的那些更新"统计。
// 子树在 DFS 先序里是连续区间 [tin[X], tin[X]+sz[X]-1],所以"覆盖某点的区间权值和"
// 用差分树状数组做:在 tin[X] 处 +v、在 tin[X]+sz[X] 处 -v,单点前缀和即为所求。
// 点值 val[L] = Fib(dep[L])*S0[L] + Fib(dep[L]+1)*S1[L],与 T[L] 共用同一次查询结果。
//
// 复杂度:预处理 O(n log n)(倍增 LCA 表),单次更新 O(log n + log k)(Fib 用倍增),
// 单次询问 O(log n)。空间 O(n log n)。n,m ≤ 1e5、k ≤ 1e15 时远超需求。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // 节点数上限
const int LOGN = 17; // log2(1e5) 向上取整,倍增 LCA 的层数
const ll MOD = 1000000007LL;
// 一个树上节点:把所有"只依赖树形状"的静态属性聚在一起,避免平行数组
struct Node {
int fa; // 父亲编号,根的父亲是 0 号哨兵(它的 pa/pb 都是 0)
int dep; // 深度 = 到根的边数(根为 0)
int tin; // DFS 先序编号(1..n),子树恰好是 [tin, tin+sz-1]
int sz; // 子树大小
ll pa; // 根到本节点的 ΣFib(dep[v]) mod MOD
ll pb; // 根到本节点的 ΣFib(dep[v]+1) mod MOD
};
Node nd[MAXN];
// 差分树状数组的一个位置:三个分量属于同一个位置,聚成 struct 而不是三个平行数组
struct BitNode {
ll c0; // 覆盖该位置的更新带来的 ΣFib(K-1)
ll c1; // 覆盖该位置的更新带来的 ΣFib(K)
ll d; // 覆盖该位置的更新带来的 Σ(c0*pa[faX] + c1*pb[faX])
};
int n, m; // 节点数、操作数
vector<int> child[MAXN]; // 每个节点的孩子表(树题用 vector 邻接表足够直观)
BitNode bit[MAXN]; // 差分树状数组,前缀和 = 覆盖当前点的更新累计量
ll fib_small[MAXN]; // fib_small[t] = Fib(t) mod MOD,深度只用 0..n+1
int up[LOGN][MAXN]; // 倍增表:up[j][v] 是 v 的第 2^j 级祖先(0 表示不存在)
int order[MAXN]; // DFS 先序序列,order[0..n-1]
int stk[MAXN]; // 迭代 DFS 的手写栈,避免递归爆栈
// 返回 (Fib(t), Fib(t+1)) mod MOD,要求 t >= 0(倍增法,O(log t))
pair<ll, ll> fib_pair(ll t) {
if (t == 0) return make_pair(0LL, 1LL);
pair<ll, ll> half = fib_pair(t >> 1);
ll a = half.first, b = half.second;
ll even = a * ((2 * b % MOD - a + MOD) % MOD) % MOD; // Fib(2i)
ll odd = (a * a + b * b) % MOD; // Fib(2i+1)
if (t & 1) return make_pair(odd, (even + odd) % MOD);
return make_pair(even, odd);
}
// Fib(t) mod MOD,允许 t 为负:Fib(-t) = (-1)^(t+1) * Fib(t)
ll fib(ll t) {
if (t >= 0) return fib_pair(t).first;
ll positive = -t;
ll value = fib_pair(positive).first;
if (positive % 2 == 0) value = (MOD - value) % MOD; // t<0 时符号为 (-1)^(positive+1)
return value;
}
// 在差分树状数组的位置 pos 处累加一个三元增量
void bit_add(int pos, ll v0, ll v1, ll v2) {
for (int i = pos; i <= n; i += i & -i) {
bit[i].c0 = (bit[i].c0 + v0) % MOD;
bit[i].c1 = (bit[i].c1 + v1) % MOD;
bit[i].d = (bit[i].d + v2) % MOD;
}
}
// 位置 pos 的三元前缀和,即"子树区间覆盖了 pos 的那些更新"的累计量
BitNode bit_query(int pos) {
BitNode res;
res.c0 = res.c1 = res.d = 0;
for (int i = pos; i > 0; i -= i & -i) {
res.c0 += bit[i].c0;
res.c1 += bit[i].c1;
res.d += bit[i].d;
}
res.c0 %= MOD; res.c1 %= MOD; res.d %= MOD;
return res;
}
// T[u] = 根到 u 链上的点权和:静态 Fib 前缀和乘累计量,再减掉差分的第三维
ll chain_sum(int u, BitNode s) {
ll res = (nd[u].pa * s.c0 + nd[u].pb * s.c1 - s.d) % MOD;
return (res % MOD + MOD) % MOD;
}
// val[u] = 点 u 当前的权值:比 chain_sum 少一个差分的 d 项(那项属于 X 上半段的修正)
ll point_value(int u, BitNode s) {
ll res = (fib_small[nd[u].dep] * s.c0 + fib_small[nd[u].dep + 1] * s.c1) % MOD;
return (res % MOD + MOD) % MOD;
}
int lca(int a, int b) {
if (nd[a].dep < nd[b].dep) swap(a, b);
int diff = nd[a].dep - nd[b].dep;
for (int j = 0; j < LOGN; ++j) {
if ((diff >> j) & 1) a = up[j][a];
}
if (a == b) return a;
for (int j = LOGN - 1; j >= 0; --j) {
if (up[j][a] != up[j][b]) {
a = up[j][a];
b = up[j][b];
}
}
return nd[a].fa;
}
int main() {
// 读入与建树
scanf("%d %d", &n, &m);
for (int i = 2; i <= n; ++i) {
scanf("%d", &nd[i].fa);
child[nd[i].fa].push_back(i);
}
// 迭代式 DFS:求先序编号 tin、深度 dep
int order_cnt = 0;
int top = 0;
stk[top++] = 1;
while (top > 0) {
int u = stk[--top];
nd[u].tin = order_cnt + 1;
order[order_cnt++] = u;
for (int i = 0; i < (int)child[u].size(); ++i) {
int v = child[u][i];
nd[v].dep = nd[u].dep + 1; // fa 读入时已存好,不必再赋
stk[top++] = v;
}
}
// 逆先序累加子树大小:儿子的 sz 一定先算好
for (int i = n - 1; i >= 0; --i) {
int u = order[i];
nd[u].sz = 1;
for (int j = 0; j < (int)child[u].size(); ++j) nd[u].sz += nd[child[u][j]].sz;
}
// Fib(0..n+1) 线性递推(深度加一最多用到 n+1)
fib_small[0] = 0;
fib_small[1] = 1;
for (int i = 2; i <= n + 1; ++i) fib_small[i] = (fib_small[i - 1] + fib_small[i - 2]) % MOD;
// 根到各点的两条 Fib 前缀和(按先序保证父亲已算过)
for (int i = 0; i < n; ++i) {
int u = order[i];
nd[u].pa = (nd[nd[u].fa].pa + fib_small[nd[u].dep]) % MOD;
nd[u].pb = (nd[nd[u].fa].pb + fib_small[nd[u].dep + 1]) % MOD;
}
// 倍增表:up[0][v] = fa[v],往上逐级翻倍
for (int v = 1; v <= n; ++v) up[0][v] = nd[v].fa;
for (int j = 1; j < LOGN; ++j) {
for (int v = 1; v <= n; ++v) up[j][v] = up[j - 1][up[j - 1][v]];
}
// 处理操作
char op[8];
for (int i = 0; i < m; ++i) {
scanf("%s", op);
if (op[0] == 'U') {
int x;
ll k;
scanf("%d %lld", &x, &k);
ll big = k - nd[x].dep; // K,可能为负
ll c1 = fib(big); // Fib(K),配 Fib(dep[v]+1)
ll c0 = fib(big - 1); // Fib(K-1),配 Fib(dep[v])
int fx = nd[x].fa; // x 的父亲(根的哨兵 0,pa/pb 均为 0)
ll d = (c0 * nd[fx].pa + c1 * nd[fx].pb) % MOD;
int tail = nd[x].tin + nd[x].sz; // 子树区间 [tin, tail-1]
bit_add(nd[x].tin, c0, c1, d);
if (tail <= n) bit_add(tail, (MOD - c0) % MOD, (MOD - c1) % MOD, (MOD - d) % MOD);
} else {
int x, y;
scanf("%d %d", &x, &y);
int l = lca(x, y);
BitNode sx = bit_query(nd[x].tin);
BitNode sy = bit_query(nd[y].tin);
BitNode sl = bit_query(nd[l].tin);
// 路径和 = T[X] + T[Y] - 2*T[L] + val[L]:L 在两条根链里各被算了一次
ll ans = (chain_sum(x, sx) + chain_sum(y, sy) - 2 * chain_sum(l, sl)
+ point_value(l, sl)) % MOD;
printf("%lld\n", (ans % MOD + MOD) % MOD);
}
}
return 0;
}复杂度
- 时间:预处理含两张倍增表与 Fib 前缀和,
; 每次 U做两次差分树状数组修改与一次倍增求 Fib,; 每次 Q做三次前缀查询与一次 LCA,。 总计 ,比"树链剖分 + 线段树"的 更省。 的大数据点上实测:C++ 每个点 s(含编译后运行,限时 2000 ms), Python 每个点 s,均无 TLE 风险。 - 空间:倍增表
,其余数组 ; main.cpp把每个点的静态属性聚成struct Node、差分树状数组的同一位置聚成struct BitNode,不写平行数组, 实测峰值内存MB,远小于 512 MB。
总结
- 恒等式是破局点:
把"每个点加不同值" 变成"两个静态序列按统一系数相加",这是本题从 走向 的唯一入口。 - 静态属性与操作参数分离:凡是只随操作变化的量(
)放差分树状数组, 只随点变化的量( 、 、 )预处理成常数,两者相乘即得答案。 - 子树 = 连续区间 → 差分;路径 = 两条根链 − 重复段 → 前缀和 + LCA。 这两条是树上区间问题的通用降维手法,本题把"点权累加"换成了"线性组合的累加"。
- 负数下标的 Fib 是最大的实现陷阱:
时 , 必须用 ;否则小 的数据点会整点 WA。 - 本题素材源带自造数据生成脚本(
data.py,含链、菊花、毛毛虫、随机树四种形态与的负数分支探针),题面为网络重建版本,出题意图与原题可能略有偏差。 随仓 std.cpp(树链剖分 + 线段树)与本题解同一数学依据,实测在全部 10 个数据点上一致, 可互为参照。
图示解析
下面用样例的第一次更新 U 1 1(
| 节点 |
加上的值 | |||||
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 | ||
| 2 | 1 | 1 | 1 | 1 | ||
| 3 | 1 | 1 | 1 | 1 | ||
| 4 | 2 | 2 | 1 | 2 | ||
| 5 | 2 | 2 | 1 | 2 |
两种算法逐行对齐:第 4 列是暴力做法"按距离算"的结果,第 7 列是正解"两个静态序列的
统一系数组合"算出的结果,数值完全一致。差别在于第 7 列只用到了点自己的深度系列值,
不需要知道
flowchart TD Q["Q X Y"] --> L["L = LCA(X,Y)"] Q --> P["T[X] + T[Y] - 2T[L] + val[L]"] P --> T1["T[u] = PA[u]·S0[u] + PB[u]·S1[u] - S2[u]"] T1 --> BIT["差分树状数组前缀和<br/>(子树区间覆盖了 u 的更新)"] U["U X k, K = k - dep[X]"] --> C["c0 = Fib(K-1), c1 = Fib(K)"] C --> ADD["tin[X] 处 +c,tin[X]+sz[X] 处 -c"] ADD --> BIT
图的上半部分是询问的化归链:路径和 → 三个根链前缀和 + LCA 处的点权 →
单点


