树上斐波那契

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

用斐波那契加法公式把按深度加 Fib(k+D) 拆成两个静态系数,子树区间差分套树状数组,路径和转为根前缀和与 LCA。

OJ: roj

题目 ID: 1765

难度:提高+/省选-

标签:数学斐波那契树状数组差分LCA倍增python

创建: 2026-10-08 00:32

更新: 2026-10-08 00:32

形式化题目

给定一棵以 11 为根的有根树 TT,共 nn 个节点,初始每个点的权值均为 00。 Fib 序列定义为 Fib(1)=Fib(2)=1Fib(1)=Fib(2)=1,且对 i⩾3i \geqslant 3 有 Fib(i)=Fib(i−1)+Fib(i−2)Fib(i)=Fib(i-1)+Fib(i-2)。 维护 mm 次操作:

  • U X k:对 XX 子树内每个节点 vv(含 XX 自己),设 vv 到 XX 的边数为 DD, 令 val[v]+=Fib(k+D)val[v] \mathrel{+}= Fib(k+D);
  • Q X Y:求 XX 到 YY 的唯一简单路径上所有节点(含端点)的权值和,模 109+710^9+7 输出。

其中 n,m⩽105n,m \leqslant 10^5,1⩽X,Y⩽n1 \leqslant X,Y \leqslant n,1⩽k⩽10151 \leqslant k \leqslant 10^{15}。

暴力解法

思路

按题面直译即可。每个点存一个权值数组 val[1..n]。

  • 修改:从 XX 出发 DFS 整棵子树,向下传一个距离 DD,把 Fib(k+D)Fib(k+D) 加到 val[v]。 由于 XX 到子树内任一点 vv 的路径必过 XX,只用深度差就能得到 DD, 不需要真的记路径。
  • 询问:先把 XX、YY 提到同一深度,再一起往上跳,途中把经过的点权加起来, 跳到同一个点后它是唯一被重复计数的点,减掉一次即可。

Fib 的项要现算:kk 最大 101510^{15},k+Dk+D 可能很大,不能线性递推, 用倍增 O(log⁡(k+D))O(\log(k+D)) 求出 (Fib(t),Fib(t+1))\big(Fib(t),Fib(t+1)\big) 即可; kk 很小时 k+Dk+D 仍非负,所以这一版还不需要处理负下标。

代码

include-code failed: ./brute.cpp

复杂度

单次修改 O(子树大小)=O(n)O(\text{子树大小})=O(n),单次询问 O(n)O(n),总计 O(nm)O(nm) (每次算 FibFib 另有 O(log⁡k)O(\log k) 的倍增代价)。 n=m=105n=m=10^5 时是 101010^{10} 量级,必然超时。

瓶颈

表面看瓶颈是"子树/路径要逐个点跑",但真正的障碍在修改的那一项:

Fib(k+D)=Fib((k−dep[X])+dep[v])Fib(k+D) = Fib\big((k - dep[X]) + dep[v]\big)

对同一次修改而言,系数 k−dep[X]k-dep[X] 是常数,但被加的值随每个点的深度 dep[v]dep[v] 变化, 每个点是不同的数。所以既不能整体打一个"加常数"的懒标记, 也不能整体打一个"乘常数"的懒标记——每个叶子要加的数都不一样。 这就是本题不能用"子树加常数 + 路径求和"套模板的原因。

正解

思路

关键观察:斐波那契加法公式把"变化的加数"变成"两个固定序列的线性组合"。 Fibonacci 有恒等式(对全体整数都成立)

Fib(a+b)=Fib(a)⋅Fib(b+1)+Fib(a−1)⋅Fib(b).Fib(a+b) = Fib(a)\cdot Fib(b+1) + Fib(a-1)\cdot Fib(b).

取 a=k−dep[X]=Ka = k - dep[X] = K(一次修改内的常数)、b=dep[v]b = dep[v](点自身的静态属性),得到

Fib(k+D)=Fib(K)⋅Fib(dep[v]+1)+Fib(K−1)⋅Fib(dep[v]),D=dep[v]−dep[X].Fib(k + D) = Fib(K)\cdot Fib(dep[v]+1) + Fib(K-1)\cdot Fib(dep[v]), \qquad D = dep[v]-dep[X].

观察重点在于:Fib(dep[v])Fib(dep[v]) 与 Fib(dep[v]+1)Fib(dep[v]+1) 只依赖深度,永远不会随操作改变; Fib(K)Fib(K)、Fib(K−1)Fib(K-1) 只依赖本次操作,对子树内所有点都一样。 于是"给区间内每个点加一个各不相同的数"被拆成了两件事—— 在子树区间上整体加 c1⋅(Fib(dep[v]+1))c_1 \cdot \big(Fib(dep[v]+1)\big) 与 c0⋅(Fib(dep[v]))c_0 \cdot \big(Fib(dep[v])\big), 两个加数序列都是预先算好的静态序列,同一操作内系数统一。

第二步:把"各类更新的加权和"沉淀成每个点上的三个累计量。 对每个点 vv,维护三个数:S0[v]=∑c0S_0[v] = \sum c_0、S1[v]=∑c1S_1[v] = \sum c_1、S2[v]=∑dS_2[v] = \sum d, 其中求和范围是所有子树区间覆盖 vv 的更新,d=c0 PA[faX]+c1 PB[faX]d = c_0\,PA[faX] + c_1\,PB[faX] (PA[w],PB[w]PA[w],PB[w] 是根到 ww 上 Fib(dep)Fib(dep)、Fib(dep+1)Fib(dep+1) 的前缀和,faXfaX 是修改点 XX 的父亲)。 此时点权就是

val[v]=Fib(dep[v])⋅S0[v]+Fib(dep[v]+1)⋅S1[v].val[v] = Fib(dep[v])\cdot S_0[v] + Fib(dep[v]+1)\cdot S_1[v].

"子树是 DFS 先序中的连续区间"这一性质让 S0,S1,S2S_0,S_1,S_2 可以统一维护: 一次更新在 tin[X]tin[X] 处 +c+c、在 tin[X]+sz[X]tin[X]+sz[X] 处 −c-c(区间差分), 某点 vv 的 S[v]S[v] 就是差分数组在 tin[v]tin[v] 处的前缀和。 三个累计量下标一致、总是一起增删,用一个三元差分树状数组即可。

第三步:询问不需要真的爬路径。 记 T[u]=∑v∈根→uval[v]T[u] = \sum_{v \in \text{根} \to u} val[v](根到 uu 的点权前缀和)。 路径 X→YX \to Y 拆成"根到 XX"与"根到 YY"两条链删除重复部分,设 L=LCA(X,Y)L = \mathrm{LCA}(X,Y):

T[X]+T[Y]=路径和+2 T[L]−val[L]  ⟹  路径和=T[X]+T[Y]−2T[L]+val[L].T[X] + T[Y] = \text{路径和} + 2\,T[L] - val[L] \;\Longrightarrow\; \text{路径和} = T[X] + T[Y] - 2T[L] + val[L].

最后一步化归:T[u]T[u] 也能用上面那三个累计量一次算出来,不必逐点求和。 把 valval 的定义代进 T[u]T[u],交换求和顺序: 更新 (X,k)(X,k) 对 T[u]T[u] 的贡献只在 u∈Xu \in X 子树时非零,而那时路径 X→uX \to u 上的 ∑Fib(dep[v])\sum Fib(dep[v]) 恰好等于 PA[u]−PA[faX]PA[u] - PA[faX](PBPB 同理),于是

T[u]=PA[u]⋅S0[u]+PB[u]⋅S1[u]−S2[u].T[u] = PA[u]\cdot S_0[u] + PB[u]\cdot S_1[u] - S_2[u].

PA[u],PB[u]PA[u],PB[u] 是静态的,S0[u],S1[u],S2[u]S_0[u],S_1[u],S_2[u] 是一次树状数组前缀查询, 所以单点 TT 值 O(log⁡n)O(\log n) 拿到,val[L]val[L] 复用 LL 的那次查询结果即可。 每次询问只查 33 个点(XX、YY、LL)、每次更新只做 22 次差分修改。

Fib 系数怎么算。 K=k−dep[X]K = k - dep[X] 可能为负(kk 很小、XX 很深时), 需要负下标延拓 Fib(−p)=(−1)p+1Fib(p)Fib(-p) = (-1)^{p+1}Fib(p),它由 Fib(m+2)=Fib(m+1)+Fib(m)Fib(m+2)=Fib(m+1)+Fib(m) 双向外推得到。 p⩽1015p \leqslant 10^{15} 不能线性递推,用倍增: 由 Fib(2i)=Fib(i)(2Fib(i+1)−Fib(i))Fib(2i)=Fib(i)\big(2Fib(i+1)-Fib(i)\big)、Fib(2i+1)=Fib(i)2+Fib(i+1)2Fib(2i+1)=Fib(i)^2+Fib(i+1)^2 自顶向下 O(log⁡p)O(\log p) 求出 (Fib(p),Fib(p+1))\big(Fib(p),Fib(p+1)\big)。

符号 含义 何时算
dep[v]dep[v] 根的深度取 00(到根的边数) 预处理
Fib(dep[v])Fib(dep[v])、Fib(dep[v]+1)Fib(dep[v]+1) 点 vv 的两条静态序列值 预处理(线性递推到 n+1n+1)
PA[w]PA[w]、PB[w]PB[w] 根到 ww 上两条静态序列的前缀和 预处理
K=k−dep[X]K = k - dep[X] 单次更新的特征量 每次 U
c0=Fib(K−1)c_0 = Fib(K-1)、c1=Fib(K)c_1 = Fib(K) 单次更新的两个系数 每次 U(倍增)
d=c0PA[faX]+c1PB[faX]d = c_0 PA[faX] + c_1 PB[faX] 差分的第三维修正值 每次 U
S0,S1,S2S_0,S_1,S_2 覆盖当前点的更新的三类累加和 差分树状数组查询

代码

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-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++ 版(同一算法):

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-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 前缀和,O(nlog⁡n+n)O(n\log n + n); 每次 U 做两次差分树状数组修改与一次倍增求 Fib,O(log⁡n+log⁡k)O(\log n + \log k); 每次 Q 做三次前缀查询与一次 LCA,O(log⁡n)O(\log n)。 总计 O((n+m)log⁡n+mlog⁡k)O\big((n+m)\log n + m\log k\big),比"树链剖分 + 线段树"的 O(mlog⁡2n)O(m\log^2 n) 更省。 n=m=105n=m=10^5 的大数据点上实测:C++ 每个点 ⩽0.14\leqslant 0.14 s(含编译后运行,限时 2000 ms), Python 每个点 ⩽1.2\leqslant 1.2 s,均无 TLE 风险。
  • 空间:倍增表 O(nlog⁡n)O(n\log n),其余数组 O(n)O(n);main.cpp 把每个点的静态属性聚成 struct Node、差分树状数组的同一位置聚成 struct BitNode,不写平行数组, 实测峰值内存 ⩽20\leqslant 20 MB,远小于 512 MB。

总结

  • 恒等式是破局点:Fib(a+b)=Fib(a)Fib(b+1)+Fib(a−1)Fib(b)Fib(a+b)=Fib(a)Fib(b+1)+Fib(a-1)Fib(b) 把"每个点加不同值" 变成"两个静态序列按统一系数相加",这是本题从 O(nm)O(nm) 走向 O(log⁡)O(\log) 的唯一入口。
  • 静态属性与操作参数分离:凡是只随操作变化的量(c0,c1c_0,c_1)放差分树状数组, 只随点变化的量(Fib(dep)Fib(dep)、PAPA、PBPB)预处理成常数,两者相乘即得答案。
  • 子树 = 连续区间 → 差分;路径 = 两条根链 − 重复段 → 前缀和 + LCA。 这两条是树上区间问题的通用降维手法,本题把"点权累加"换成了"线性组合的累加"。
  • 负数下标的 Fib 是最大的实现陷阱:k<dep[X]k<dep[X] 时 K<0K<0, 必须用 Fib(−p)=(−1)p+1Fib(p)Fib(-p)=(-1)^{p+1}Fib(p);否则小 kk 的数据点会整点 WA。
  • 本题素材源带自造数据生成脚本(data.py,含链、菊花、毛毛虫、随机树四种形态与 k=1k=1 的负数分支探针),题面为网络重建版本,出题意图与原题可能略有偏差。 随仓 std.cpp(树链剖分 + 线段树)与本题解同一数学依据,实测在全部 10 个数据点上一致, 可互为参照。

图示解析

下面用样例的第一次更新 U 1 1(X=1X=1,K=1−dep[1]=1K=1-dep[1]=1,故 c0=Fib(0)=0c_0=Fib(0)=0、 c1=Fib(1)=1c_1=Fib(1)=1)说明"一条更新如何影响询问":树为 11 的孩子 {2,3}\{2,3\}、 22 的孩子 {4,5}\{4,5\},深度分别是 0,1,1,2,20,1,1,2,2。

节点 vv dep[v]dep[v] DD 加上的值 Fib(dep[v])Fib(dep[v]) Fib(dep[v]+1)Fib(dep[v]+1) c0Fib(dep)+c1Fib(dep+1)c_0Fib(dep)+c_1Fib(dep+1)
1 0 0 Fib(1)=1Fib(1)=1 0 1 0⋅0+1⋅1=10\cdot 0+1\cdot 1=1
2 1 1 Fib(2)=1Fib(2)=1 1 1 0⋅1+1⋅1=10\cdot 1+1\cdot 1=1
3 1 1 Fib(2)=1Fib(2)=1 1 1 0⋅1+1⋅1=10\cdot 1+1\cdot 1=1
4 2 2 Fib(3)=2Fib(3)=2 1 2 0⋅1+1⋅2=20\cdot 1+1\cdot 2=2
5 2 2 Fib(3)=2Fib(3)=2 1 2 0⋅1+1⋅2=20\cdot 1+1\cdot 2=2

两种算法逐行对齐:第 4 列是暴力做法"按距离算"的结果,第 7 列是正解"两个静态序列的 统一系数组合"算出的结果,数值完全一致。差别在于第 7 列只用到了点自己的深度系列值, 不需要知道 XX 是谁、也不需要 DD,因此一次区间加权就把整棵子树处理完了。

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 处的点权 → 单点 TT 用静态前缀和乘上树状数组查询结果表示。下半部分是更新的入口: 先由 KK 求出两个系数,再把它们作为区间差分的增量注入同一棵树状数组。 两半唯一交汇的地方就是那个差分树状数组——更新只在区间两端各记一笔, 询问只查三个点的前缀和,这就是"单次操作与树的大小无关"的原因。