P8353 [SDOI/SXOI2022] 无处存储

存下每个点的父亲信息 \(fa\) 和 点权 \(w\) 就已经用去近 \(54 \text{ MiB}\) 了，树剖似得彻彻底底。

考虑树分块：随机选定 \(\sqrt n\) 个点作为关键点建虚树，这样每个点向上走到关键点的步数期望为 \(\sqrt n\)，然后每个关键点存原树上从它到它虚树上的父亲结点的信息。

dfs 似了，因为它占栈空间，跑一遍就 MLE，那怎么建虚树？

可以枚举 \(\sqrt n\) 个关键点，每个点打标记并往上跳，遇到打过标记的点就连边然后终止，时间复杂度 \(\mathcal O(n)\)。

还有一个细节是用数组存标记会爆空间，bitset！

修改和查询可以用树上差分的思路拆分成四个，这样就只用考虑起始段的特殊情况了。

需要支持的操作：找到找到包含当前点的块、求两个点的 LCA。

• 可以对每个关键点存他往任意一个儿子方向的下一个关键点，每次向上跳再跳下去就好了，时间复杂度 \(\mathcal O(\sqrt n)\)。
• 找 LCA 的时候类似于倍增，只不过是跳块罢了。总体细节不少的，难写呃呃呃呃呃呃呃呃啊啊啊啊啊啊啊啊啊！！

总时间复杂度是 \(\mathcal O(q \sqrt n)\)，人傻常数大。

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 7e6 + 10, SN = 6e3;

namespace INPUT_SPACE{
	const int S=(1<<20)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; }
	inline unsigned int inn() { unsigned int x,ch;while((ch=gc())<'0'||ch>'9');x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x; }
}using INPUT_SPACE::inn;

int n, m, q, fa[N], anc[N], p[SN];
uint w[N], d[SN], s[SN], add[SN];
mt19937 rnd(19260817);
bitset<N> key, vis;
vector<uint> G[SN], H[SN];
unordered_map<uint, uint> id, son[SN];

inline int dep(int u) {
    int res = 0;
    while (!key[u]) u = fa[u], res++;
    return res + d[id[u]];
}

inline int getbel(int u) {
    if (key[u]) return id[u];
    while (!key[fa[u]]) u = fa[u];
    return son[id[fa[u]]][u];
}

inline void pushdown(int x, int y) {
    if (!add[x]) return;
    for (int i = p[x]; i != p[y]; i = fa[i]) w[i] += add[x];
    add[x] = 0;
}

inline void upd(int u, uint c) {
    if (!u) return;
    while (!vis[u]) w[u] += c, u = fa[u];
    if (!key[u]) {
        int down = getbel(u), up = anc[down];
        pushdown(down, up);
        for (int i = u; i != p[up]; i = fa[i]) w[i] += c, s[down] += c;
        u = up;
    } else u = id[u];
    while (u) s[u] += c * (d[u] - d[anc[u]]), add[u] += c, u = anc[u];
}

inline uint qry(int u) {
    if (!u) return 0;
    uint res = 0;
    while (!vis[u]) res += w[u], u = fa[u];
    if (!key[u]) {
        int down = getbel(u), up = anc[down];
        pushdown(down, up);
        for (int i = u; i != p[up]; i = fa[i]) res += w[i];
        u = up;
    } else u = id[u];
    while (u) res += s[u], u = anc[u];
    return res;
}

inline int keyLCA(int u, int v) {
    assert(u != 0 && v != 0);
    while (u != v) d[u] > d[v] ? u = anc[u] : v = anc[v];
    return u;
}

inline int LCA(int u, int v) {
    int x = u, y = v, du = dep(u), dv = dep(v);
    while (!vis[x]) x = fa[x]; while (!vis[y]) y = fa[y];
    if (x == y) {
        while (u != v) du > dv ? (u = fa[u], du--) : (v = fa[v], dv--);
        return u;
    }
    u = x, v = y; x = key[x] ? id[x] : getbel(u); y = key[y] ? id[y] : getbel(y);
    if (x == y) return dep(u) < dep(v) ? u : v;
    int lca = keyLCA(x, y);
    if (lca == x) return u;
    if (lca == y) return v;
    return p[lca];
}

inline void upd(int u, int v, uint c) {
    int lca = LCA(u, v);
    upd(u, c), upd(v, c), upd(lca, -c), upd(fa[lca], -c);
}

inline uint qry(int u, int v) {
    int lca = LCA(u, v);
    return qry(u) + qry(v) - qry(lca) - qry(fa[lca]);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    inn(), n = inn(), q = inn(), m = sqrt(n);
    uint A, B, C; A = inn(), B = inn(), C = inn(), w[0] = inn();
    for (int i = 1; i <= n; i++) w[i] = A * w[i - 1] * w[i - 1] + B * w[i - 1] + C;
    for (int i = 2; i <= n; i++) fa[i] = inn();
    key[p[1] = 1] = 1;
    for (int i = 2; i <= m; i++) {
        do p[i] = rnd() % n + 1;
        while (key[p[i]]);
        key[p[i]] = 1;
    }
    sort(p + 1, p + m + 1); vis[1] = 1;
    for (int i = 2, u; i <= m; i++) {
        for (u = p[i]; !vis[u]; u = fa[u]) vis[u] = 1;
        if (!key[u]) key[p[++m] = u] = 1;
    }
    sort(p + 1, p + m + 1); for (int i = 1; i <= m; i++) id[p[i]] = i;
    s[1] = w[1], d[1] = 1;
    for (int i = 2, v; i <= m; i++) {
        s[i] = w[p[i]], d[i] = 1;
        for (anc[i] = fa[p[i]], v = p[i]; !key[anc[i]]; v = anc[i], anc[i] = fa[anc[i]]) s[i] += w[anc[i]], d[i]++;
        d[i] += d[anc[i] = id[anc[i]]], son[anc[i]][v] = i;
    }
    uint op, x, y, v, lastans = 0;
    while (q--) {
        op = inn(), x = inn() ^ lastans, y = inn() ^ lastans;
        if (op) cout << (lastans = qry(x, y)) << '\n', lastans &= (1 << 20) - 1;
        else v = inn() ^ lastans, upd(x, y, v);
    }
    return 0;
}