思路与算法

重链剖分保持子树连续。更新x,k时令t=k-depth(x)，用F(k+dist(x,v))=F(t-1)F(depth(v))+F(t)F(depth(v)+1)。线段树预存两组深度基函数区间和，懒标记为两系数；子树更新作区间加，路径查询按重链求和。大下标用快速倍增。

正确性说明

斐波那契加法公式对整数下标成立，负下标由F(-n)=(-1)^(n+1)F(n)补全。子树内距离等于深度差，故每个顶点更新值恰由两基函数线性组合给出。线段树分配律与重链无重覆盖保持各点累积值，查询即所求路径和。

复杂度

基函数、树链和建树O(N)，U次更新O(U(logk+logN))，Q次查询O(Qlog²N)，空间O(N)，初始化均计入。

易错点

k-depth(x)可能为负，不能直接调用仅支持非负的倍增。下标可达10^15，用64位；负号和所有系数须规范化到模域，子树区间必须包含x。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct HLD {
    int n;
    vector<vector<int>> g;
    vector<int> p, dep, sz, heavy, top, id, rev, ord;
    HLD(int n) : n(n), g(n), p(n, -1), dep(n), sz(n, 1), heavy(n, -1), top(n), id(n), rev(n) {
    }
    void build() {
        ord = {0};
        for (size_t i = 0; i < ord.size(); i++) {
            int u = ord[i];
            for (int v : g[u])
                if (v != p[u]) {
                    p[v] = u;
                    dep[v] = dep[u] + 1;
                    ord.push_back(v);
                }
        }
        for (int i = n - 1; i > 0; i--) {
            int u = ord[i], v = p[u];
            sz[v] += sz[u];
            if (heavy[v] < 0 || sz[u] > sz[heavy[v]])
                heavy[v] = u;
        }
        int timer = 0;
        vector<pair<int, int>> st(1, {0, 0});
        while (!st.empty()) {
            auto x = st.back();
            st.pop_back();
            for (int u = x.first; u >= 0; u = heavy[u]) {
                top[u] = x.second;
                id[u] = timer;
                rev[timer++] = u;
                for (int v : g[u])
                    if (v != p[u] && v != heavy[u])
                        st.push_back({v, v});
            }
        }
    }
    vector<array<int, 3>> path(int a, int b) {
        vector<array<int, 3>> L, R;
        while (top[a] != top[b]) {
            if (dep[top[a]] >= dep[top[b]]) {
                L.push_back({id[top[a]], id[a], 0});
                a = p[top[a]];
            } else {
                R.push_back({id[top[b]], id[b], 1});
                b = p[top[b]];
            }
        }
        if (dep[a] >= dep[b])
            L.push_back({id[b], id[a], 0});
        else
            L.push_back({id[a], id[b], 1});
        reverse(R.begin(), R.end());
        L.insert(L.end(), R.begin(), R.end());
        return L;
    }
};
const long long MOD = 1000000007;
pair<long long, long long> fib(long long n) {
    if (!n)
        return {0, 1};
    auto p = fib(n / 2);
    long long a = p.first, b = p.second, c = a * ((2 * b - a + MOD) % MOD) % MOD,
              d = (a * a + b * b) % MOD;
    return n % 2 ? make_pair(d, (c + d) % MOD) : make_pair(c, d);
}
long long F(long long n) {
    if (n >= 0)
        return fib(n).first;
    long long v = fib(-n).first;
    return (-n) % 2 ? v : (MOD - v) % MOD;
}
struct Seg {
    int n;
    vector<long long> sum, B1, B2, L1, L2;
    Seg(vector<long long> &a, vector<long long> &b)
        : n(a.size()), sum(4 * n), B1(4 * n), B2(4 * n), L1(4 * n), L2(4 * n) {
        build(1, 0, n - 1, a, b);
    }
    void build(int v, int l, int r, vector<long long> &a, vector<long long> &b) {
        if (l == r) {
            B1[v] = a[l];
            B2[v] = b[l];
            return;
        }
        int m = (l + r) / 2;
        build(v * 2, l, m, a, b);
        build(v * 2 + 1, m + 1, r, a, b);
        B1[v] = (B1[v * 2] + B1[v * 2 + 1]) % MOD;
        B2[v] = (B2[v * 2] + B2[v * 2 + 1]) % MOD;
    }
    void apply(int v, long long a, long long b) {
        sum[v] = (sum[v] + a * B1[v] + b * B2[v]) % MOD;
        L1[v] = (L1[v] + a) % MOD;
        L2[v] = (L2[v] + b) % MOD;
    }
    void push(int v) {
        apply(v * 2, L1[v], L2[v]);
        apply(v * 2 + 1, L1[v], L2[v]);
        L1[v] = L2[v] = 0;
    }
    void update(int v, int l, int r, int a, int b, long long x, long long y) {
        if (a <= l && r <= b) {
            apply(v, x, y);
            return;
        }
        push(v);
        int m = (l + r) / 2;
        if (a <= m)
            update(v * 2, l, m, a, b, x, y);
        if (b > m)
            update(v * 2 + 1, m + 1, r, a, b, x, y);
        sum[v] = (sum[v * 2] + sum[v * 2 + 1]) % MOD;
    }
    long long query(int v, int l, int r, int a, int b) {
        if (a <= l && r <= b)
            return sum[v];
        push(v);
        int m = (l + r) / 2;
        long long ans = 0;
        if (a <= m)
            ans += query(v * 2, l, m, a, b);
        if (b > m)
            ans += query(v * 2 + 1, m + 1, r, a, b);
        return ans % MOD;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    HLD h(n);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        h.g[--p].push_back(i);
        h.g[i].push_back(p);
    }
    h.build();
    vector<long long> f(n + 2), a(n), b(n);
    f[1] = 1;
    for (int i = 2; i < n + 2; i++)
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    for (int u = 0; u < n; u++) {
        a[h.id[u]] = f[h.dep[u]];
        b[h.id[u]] = f[h.dep[u] + 1];
    }
    Seg s(a, b);
    while (m--) {
        string op;
        int x;
        long long k;
        cin >> op >> x >> k;
        --x;
        if (op == "U") {
            long long t = k - h.dep[x];
            s.update(1, 0, n - 1, h.id[x], h.id[x] + h.sz[x] - 1, F(t - 1), F(t));
        } else {
            long long ans = 0;
            for (auto t : h.path(x, (int)k - 1))
                ans = (ans + s.query(1, 0, n - 1, t[0], t[1])) % MOD;
            cout << ans << '\n';
        }
    }
}