RE 30pts 求助 /kk

rt，只过了 <= 1 的点 /kk

Code：

#include <climits>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
typedef unsigned long long ull;
const int N = 2e5 + 5;
const ull inf = ULLONG_MAX;
const ull I = 1llu;

struct dataTuple {
    ull f[2], g[2];
    inline void flip() {
        swap(f[0], g[0]);
        swap(f[1], g[1]);
    }
};

inline dataTuple merge(const dataTuple& a, const dataTuple& b) {
    dataTuple ret;
    ret.f[0] = (a.f[0] & b.f[1]) | (~a.f[0] & b.f[0]);
    ret.f[1] = (a.f[1] & b.f[1]) | (~a.f[1] & b.f[0]);
    ret.g[0] = (b.g[0] & a.g[1]) | (~b.g[0] & a.g[0]);
    ret.g[1] = (b.g[1] & a.g[1]) | (~b.g[1] & a.g[0]);
    return ret;
}

int n, m, k;
vector<int> G[N];
int opt[N];
ull val[N];

int fa[N], siz[N], dep[N];
int wson[N], wtop[N];
int dfn[N], ref[N], timer = 0;

void Dfs1(int x, int f) {
    fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1;
    for (auto y : G[x]) if (y != f) {
        Dfs1(y, x), siz[x] += siz[y];
        if (siz[wson[x]] < siz[y]) wson[x] = y;
    }
}
void Dfs2(int x, int t) {
    wtop[x] = t, ref[dfn[x] = ++timer] = x;
    if (!wson[x]) return;
    Dfs2(wson[x], t);
    for (auto y : G[x]) if (y != fa[x] && y != wson[x])
        Dfs2(y, y);
}

const int S = N << 2;
int L[S], R[S];
dataTuple A[S];

inline ull calc(ull v, int x) {
    if (opt[x] == 1) return v & val[x];
    if (opt[x] == 2) return v | val[x];
    if (opt[x] == 3) return v ^ val[x];
}

#define mid ((L[x] + R[x]) >> 1)
void build(int l, int r, int x = 1) {
    L[x] = l, R[x] = r;
    if (l == r) {
        A[x].f[0] = A[x].g[0] = calc(0, ref[l]);
        A[x].f[1] = A[x].g[1] = calc(inf, ref[l]);
        return;
    }
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    A[x] = merge(A[x << 1], A[x << 1 | 1]);
}
void modify(int p, int x = 1) {
    if (L[x] == R[x]) {
        A[x].f[0] = A[x].g[0] = calc(0, ref[p]);
        A[x].f[1] = A[x].g[1] = calc(inf, ref[p]);
        return;
    }
    modify(p, x << 1 | (p > mid));
    A[x] = merge(A[x << 1], A[x << 1 | 1]);
}
dataTuple get(int l, int r, int x = 1) {
    if (l <= L[x] && R[x] <= r) return A[x];
    if (r <= mid) return get(l, r, x << 1);
    else if (l > mid) return get(l, r, x << 1 | 1);
    return merge(get(l, r, x << 1), get(l, r, x << 1 | 1));
}
#undef mid

dataTuple rec1[N];
dataTuple rec2[N];
int cnt1, cnt2;

dataTuple query(int x, int y) {
    cnt1 = cnt2 = 0;
    while (wtop[x] != wtop[y]) {
        if (dep[wtop[x]] >= dep[wtop[y]]) {
            rec1[++cnt1] = get(dfn[wtop[x]], dfn[x]);
            x = fa[wtop[x]];
        } else {
            rec2[++cnt2] = get(dfn[wtop[y]], dfn[y]);
            y = fa[wtop[y]];
        }
    }
    if (dep[x] > dep[y]) rec1[++cnt1] = get(dfn[y], dfn[x]);
    else rec2[++cnt2] = get(dfn[x], dfn[y]);

    dataTuple ret;
    for (int i = 1; i <= cnt1; i++) rec1[i].flip();
    if (cnt1) {
        ret = rec1[1];
        for (int i = 2; i <= cnt1; i++) ret = merge(ret, rec1[i]);
        if (cnt2) ret = merge(ret, rec2[cnt2]);
    } else ret = rec2[cnt2];
    for (int i = cnt2 - 1; i; i--) ret = merge(ret, rec2[i]);

    return ret;
}

signed main() {
    //freopen("t.in", "r", stdin);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        cin >> opt[i] >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    Dfs1(1, 0);
    Dfs2(1, 1);
    build(1, n);

    while (m--) {
        int cmd, x, y; ull z;
        cin >> cmd >> x >> y >> z;
        if (cmd == 1) {
            dataTuple w = query(x, y);
            ull ans = 0llu;
            for (ull i = 63; ~i; i--) {
                ull x = w.f[0] >> i & I, y = w.f[1] >> i & I;
                if (x) ans |= (I << i);
                else if (y && z >= (I << i))
                    ans |= (I << i), z -= (I << i);
            }
            cout << ans << '\n';
        } else {
            opt[x] = y, val[x] = z;
            modify(dfn[x]);
        }
    }
}

希望不会有无意义回复