\(\text{Problem}\)

术树数

\(\text{Summary}\)

这题有许多优美的结论，并加深了对线性基的理解

图论中非常有用的结论（路径可重）：

1.包含一个点的简单环张成了包含一个点的所有环
2.考虑图的任意一棵生成树，取两点树上路径权值和异或上任意环的异或值构成了这两点间的所有路径
3.任取一条路径，任意异或一个环，可以生成所有路径

若是 \(K\) 进制异或，把一条边看成一个环结论仍然成立
于是只要把所有简单环扔进线性基，询问时将路径异或和扔进线性基查询最小异或和即可

\(K\) 进制线性基的维护就很高科技了，不想说了

\(\text{warning:}\) 做扩展欧几里得时传参最好是 long long 类型，很容易爆 int

\(\text{Code}\)

#include <bits/stdc++.h> 
#define IN inline
using namespace std;

template<typename Tp>
IN void read(Tp &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
    if (f) x = ~x + 1;
}

typedef long long LL;
const int LG = 17, N = 2e5 + 5;
int fa[N][LG + 2], dep[N];

IN int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for(int i = LG; ~i; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for(int i = LG; ~i; i--) if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

namespace K_Base {
    int bit[25], K, m, val[N];
    IN void init(){bit[0] = 1; for(int i = 1; i < m; i++) bit[i] = bit[i - 1] * K;}
    IN int getbit(int x, int p){return x / bit[p] % K;}
    
    IN int add(int x, int y) {
        int z = 0;
        for(int i = 0, u; i < m; i++) {
            u = getbit(x, i); if ((u += getbit(y, i)) >= K) u -= K; z += u * bit[i];
        }
        return z;
    }
    IN int reduce(int x, int y) {
        int z = 0;
        for(int i = 0, u; i < m; i++) {
            u = getbit(x, i); if ((u -= getbit(y, i)) < 0) u += K; z += u * bit[i];
        }
        return z;
    }
    IN int mul(int x, LL y) {
        y %= K; if (y < 0) y += K; int z = 0;
        for(int i = 0; i < m; i++) z += getbit(x, i) * y % K * bit[i];
        return z;
    }
    IN int exgcd(int a, int b, LL &x, LL &y) {
        if (!b) return x = 1, y = 0, a;
        int d = exgcd(b, a % b, y, x);
        return y -= (LL)a / b * x, d;
    }
    
    struct LinearBasis {
        int p[25];
        IN void insert(int x) {
            for(int i = m - 1; ~i; i--) if (getbit(x, i)) {
                if (!p[i]) {
                    LL t1 = 0, t2 = 0, d = exgcd(getbit(x, i), K, t1, t2);
                    p[i] = mul(x, t1), x = mul(x, K / d);
                }
                for(; getbit(x, i); p[i] = reduce(p[i], mul(x, getbit(p[i], i) / getbit(x, i))), swap(p[i], x));
            }
        }
        IN int query(int x) {
            for(int i = m - 1; ~i; i--) {
                int u = getbit(x, i);
                if (u && p[i]) x = reduce(x, mul(p[i], u / getbit(p[i], i)));
            }
            return x;
        }
    }bs;
   
    IN int getVal(int x, int y){return reduce(add(val[x], val[y]), mul(val[LCA(x, y)], 2));}
}
using namespace K_Base;

int main() {
    int q, cnt = 1; read(q), read(K), read(m), init();
    for(int op, x, y, v, z; q; --q) {
        read(op);
        if (op == 1) {
            read(x), read(v), fa[++cnt][0] = x, val[cnt] = add(val[x], v), dep[cnt] = dep[x] + 1;
            for(int i = 1; i <= LG; i++)
                if (fa[cnt][i - 1]) fa[cnt][i] = fa[fa[cnt][i - 1]][i - 1]; else break;
            bs.insert(mul(v, 2));
        }
        else if (op == 2) read(x), read(y), read(v), bs.insert(add(v, getVal(x, y)));
        else read(x), read(y), printf("%d\n", bs.query(getVal(x, y)));
    }
}