萌新求助，卡不动了

没有写树剖，以为 LCT 会比树剖快，所以写了 LCT。时间复杂度虽然是 \mathcal{O}(m(\log n + k))，但是硬是跑不过，一直在 270ms 上下徘徊，快读加上了，我能优化的细节都优化掉了。有无这题写 LCT 的老哥能帮帮我 /kel/kel

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

using u64 = unsigned long long;

const u64 U = (u64) -1;

const int N = 1e5 + 10;

namespace io {
    const int __SIZE = (1 << 21) + 1;
    char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
    #define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
    inline void gc (char &x) { x = Gc(); }
    inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
    inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
    inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
        for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
    template <class I> inline bool gi (I &x) { _eof = 0;
        for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
        for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
    template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;

int n, m, k;
vector <int> e[N];

struct node {
  u64 val[2];
  u64 operator [] (const int &x) { return val[x]; }
  node(u64 x = 0, u64 y = 0) { val[0] = x, val[1] = y; }
} ;

namespace LCT {

  bool tag[N];
  int fa[N], son[N][2];
  node w[N], dat[N], rev[N];

  #define ls son[u][0]
  #define rs son[u][1]

  node merge(node mask, node trs) {
    return (node) { (~mask[0] & trs[0]) | (mask[0] & trs[1]), (~mask[1] & trs[0]) | (mask[1] & trs[1]) };
  }

  node calc(int op, u64 mask) {
    if (op == 1) return (node) { 0, mask };
    else if (op == 2) return (node) { mask, U };
    else return (node) { mask, ~mask };
  }

  void maintain(int u) {
    dat[u] = (node) { (u64) 0, U };
    if (ls) dat[u] = merge(dat[u], dat[ls]);
    dat[u] = merge(dat[u], w[u]);
    if (rs) dat[u] = merge(dat[u], dat[rs]);
    rev[u] = (node) { (u64) 0, U };
    if (rs) rev[u] = merge(rev[u], rev[rs]);
    rev[u] = merge(rev[u], w[u]);
    if (ls) rev[u] = merge(rev[u], rev[ls]);
  }

  void pushdown(int u) {
    if (!tag[u]) return;
    tag[ls] ^= true, tag[rs] ^= true, swap(ls, rs), tag[u] = false;
    swap(dat[ls], rev[ls]), swap(dat[rs], rev[rs]);
  }

  int which(int u) { return u == son[fa[u]][1]; }
  bool isroot(int u) { return (u != son[fa[u]][0]) && (u != son[fa[u]][1]); }
  void update(int u) { if (!isroot(u)) update(fa[u]); pushdown(u); }

  void rotate(int u) {
    int v = fa[u], w = fa[v], p = which(u);
    fa[son[u][p ^ 1]] = v, son[v][p] = son[u][p ^ 1];
    fa[u] = w; if (!isroot(v)) son[w][which(v)] = u;
    fa[v] = u, son[u][p ^ 1] = v;
    maintain(v), maintain(u);
  }

  void splay(int u) {
    update(u);
    for (int v = fa[u]; !isroot(u); rotate(u), v = fa[u]) {
      if (!isroot(v)) rotate(which(v) == which(u) ? v : u);
    }
  }

  void access(int u) { for (int v = 0; u; v = u, u = fa[u]) splay(u), rs = v, maintain(u); }
  void makeroot(int u) { access(u), splay(u), tag[u] ^= true, swap(dat[u], rev[u]), pushdown(u); }
  void split(int u, int v) { makeroot(u), access(v), splay(v); }
  void link(int u, int v) { makeroot(u), fa[u] = v; }

}

using namespace LCT;

int main() {
  gi(n), gi(m), gi(k);
  rep(i, 1, n) {
    int op; u64 z;
    gi(op), gi(z);
    w[i] = calc(op, z), maintain(i);
  }
  rep(i, 1, n - 1) {
    int u, v;
    gi(u), gi(v);
    link(u, v);
  }
  while (m --) {
    int op, x, y; u64 z;
    gi(op), gi(x), gi(y), gi(z);
    if (op == 1) {
      split(x, y);
      node res = dat[y];
      u64 ans = 0;
      for (int i = k - 1, flag = 1; ~i; -- i) {
        if (!flag) {
          u64 lim = (1ull << i + 1) - 1;
          ans |= (res[0] & lim) | (res[1] & lim);
          break;
        }
        if (!((z >> i) & 1) && flag) ans |= res[0] & (1ull << i);
        else {
          if (!((res[0] >> i) & 1) && (res[1] >> i) & 1) ans |= 1ull << i;
          else ans |= res[0] & (1ull << i), flag = 0;
        }
      }
      print(ans), pc(10);
    }
    else {
      access(x), w[x] = calc(y, z), maintain(x);
    }
  }
  return 0;
}