写码30min，调码3h的题。。
好在最后查出来了
else T.modify(, , n, x, y, z);
改成了
else T.modify(, , n, mark[x], y, z);
然后$40\rightarrow 100$
#include <bits/stdc++.h> using namespace std; #define re register
#define rep(i, a, b) for (re int i = a; i <= b; ++i)
#define repd(i, a, b) for (re int i = a; i >= b; --i)
#define For(i, a, b, s) for (re int i = a; i <= b; s)
#define maxx(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
#define LL long long
#define INF (1 << 30) #define Finline __inline__ __attribute__ ((always_inline))
extern Finline char get_char(){
static char buf[], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, , , stdin), p1 == p2) ? EOF : *p1 ++;
} template <typename T>
inline void read(T &w) {
w = ; char c = get_char();
while (!isdigit(c)) c = get_char();
while (isdigit(c)) w = (w << ) + (w << ) + (c ^ ), c = get_char();
} const int maxn = 1e5 + ; int n, m, k; struct Node {
unsigned LL v;
int opt;
} a[maxn], b[maxn]; struct Edge {
int u, v, pre;
} e[maxn << ];
int ec, G[maxn];
void init() { ec = ; memset(G, -, sizeof(G)); }
void add(int u, int v) { e[ec++] = (Edge){u, v, G[u]}; G[u] = ec-; }
#define iter(i, u) for (register int i = G[u]; i != -1; i = e[i].pre) int par[maxn], topf[maxn], son[maxn], link[maxn], mark[maxn], dep[maxn], cnt;
void dfs1(int u, int fa) {
par[u] = fa; son[u] = ; link[u] = u; dep[u] = dep[fa]+;
iter(i, u)
if (e[i].v != fa) {
dfs1(e[i].v, u);
if (son[e[i].v] >= son[link[u]]) link[u] = e[i].v;
son[u] += son[e[i].v];
}
}
void dfs2(int u, int fa, int head) {
mark[u] = ++cnt; topf[u] = head; a[cnt] = b[u];
if (link[u] != u) dfs2(link[u], u, head);
iter(i, u)
if (e[i].v != fa && e[i].v != link[u])
dfs2(e[i].v, u, e[i].v);
}
// opt: 1->& 2->| 3->^
inline unsigned LL calc(unsigned LL a, unsigned LL b, int opt) {
if (opt == ) return a & b;
else if (opt == ) return a | b;
else return a ^ b;
} #define connect(v, a, b) (((v)&(b))|(~(v)&(a))) struct Seg_T {
#define lson (o << 1)
#define rson (o << 1 | 1)
unsigned LL l0[maxn << ], l1[maxn << ], r0[maxn << ], r1[maxn << ];
void pushup(int o) {
l0[o] = connect(l0[lson], l0[rson], l1[rson]);
l1[o] = connect(l1[lson], l0[rson], l1[rson]);
r0[o] = connect(r0[rson], r0[lson], r1[lson]);
r1[o] = connect(r1[rson], r0[lson], r1[lson]);
}
void build(int o, int l, int r) {
if (l == r) {
l0[o] = r0[o] = calc((unsigned LL), a[l].v, a[l].opt);
l1[o] = r1[o] = calc(~(unsigned LL), a[l].v, a[l].opt);
return;
}
int mid = (l + r) >> ;
build(lson, l, mid), build(rson, mid+, r);
pushup(o);
}
void modify(int o, int l, int r, int p, int opt, unsigned LL v) {
if (l == r) {
l0[o] = r0[o] = calc((unsigned LL), v, opt);
l1[o] = r1[o] = calc(~(unsigned LL), v, opt);
return;
}
int mid = (l + r) >> ;
if (p <= mid) modify(lson, l, mid, p, opt, v); else modify(rson, mid+, r, p, opt, v);
pushup(o);
}
void lquery(int o, int l, int r, int ql, int qr, unsigned LL &L0, unsigned LL &L1) {
if (ql <= l && r <= qr) {
L0 = connect(L0, l0[o], l1[o]);
L1 = connect(L1, l0[o], l1[o]);
return;
}
int mid = (l + r) >> ;
if (ql <= mid) lquery(lson, l, mid, ql, qr, L0, L1);
if (mid < qr) lquery(rson, mid+, r, ql, qr, L0, L1);
}
void rquery(int o, int l, int r, int ql, int qr, unsigned LL &R0, unsigned LL &R1) {
if (ql <= l && r <= qr) {
R0 = connect(R0, r0[o], r1[o]);
R1 = connect(R1, r0[o], r1[o]);
return;
}
int mid = (l + r) >> ;
if (mid < qr) rquery(rson, mid+, r, ql, qr, R0, R1);
if (ql <= mid) rquery(lson, l, mid, ql, qr, R0, R1);
}
} T; #define swap(a, b) a ^= b ^= a ^= b
int s[maxn], size = ; unsigned LL query_link(int x, int y, unsigned LL z) {
unsigned LL l0 = , l1 = ~l0, r0 = , r1 = ~r0;
while (topf[x] != topf[y]) {
if (dep[topf[x]] > dep[topf[y]]) {
T.rquery(, , n, mark[topf[x]], mark[x], l0, l1);
x = par[topf[x]];
} else {
unsigned LL l = , r = ~l;
T.lquery(, , n, mark[topf[y]], mark[y], l, r);
l = connect(l, r0, r1);
r = connect(r, r0, r1);
r0 = l, r1 = r;
y = par[topf[y]];
}
}
if (dep[x] > dep[y]) T.rquery(, , n, mark[y], mark[x], l0, l1);
else T.lquery(, , n, mark[x], mark[y], l0, l1);
l0 = connect(l0, r0, r1); l1 = connect(l1, r0, r1);
int flag = ; unsigned LL res = , bit;
repd(i, k-, ) {
bit = (unsigned LL) << i;
if (l0 & bit) res |= bit;
if (flag) {
if (z & bit) {
if (!(l0 & bit) && (l1 & bit)) res |= bit;
else flag = ;
}
} else
if (!(l0 & bit) && (l1 & bit)) res |= bit;
}
return res;
} int main() {
init();
read(n), read(m), read(k);
rep(i, , n) read(b[i].opt), read(b[i].v);
rep(i, , n-) {
int u, v; read(u), read(v);
add(u, v), add(v, u);
}
dfs1(, ), dfs2(, , );
T.build(, , n);
rep(i, , m) {
int Q, x, y; unsigned LL z; read(Q), read(x), read(y), read(z);
if (Q == ) printf("%llu\n", query_link(x, y, z));
else T.modify(, , n, mark[x], y, z);
}
return ;
}