题目思路

首先，原题是个傻逼题，所以这题也不会难

我们考虑每个点单独作为序列时的答案ans0,ans1ans0, ans1ans0,ans1，那么序列上树后我们需要考虑区间合并：假设带合并的两个答案分别为a,ba, ba,b，那么合并就是：

a.ans0a.ans0a.ans0 的 第 kkk 位为 000，并且 b.ans0b.ans0b.ans0 的第 kkk 位为 111 或者 a.ans0a.ans0a.ans0 的第 kkk 位为 111 而且 b.ans1b.ans1b.ans1 的第 kkk 位为 111，此时合并后 ans0ans0ans0 第 kkk 位仍为111。类似的可以推出ans1ans1ans1的合并条件。

然后考虑序列上树，需要树剖来算答案。然后可以用LCT维护这个东西，但是发现makeRootmakeRootmakeRoot操作会反转子树，因此需要额外维护每个区间的正反合并序答案，并在交换儿子的时候交换答案。

那么又是一个可以快速A掉的题。

另外，要吸氧

Code

#include 
#define int unsigned long long
#define ull unsigned long long
#define endl '\n'
using namespace std;const int N = 1e6 + 10;namespace LCT{#define ls ch[x][0]#define rs ch[x][1]struct Info {ull ans0, ans1;void assign(int op, int x) {if(op == 1) ans0 = 0, ans1 = x;if(op == 2) ans0 = x, ans1 = ~0;if(op == 3) ans0 = x, ans1 = ~x;}friend Info operator+ (Info a, Info b) {return Info {(~a.ans0 & b.ans0) | (a.ans0 & b.ans1),(~a.ans1 & b.ans0) | (a.ans1 & b.ans1) };}} ans[N], fnt[N], bak[N];int ch[N][2], f[N], val[N], tag[N], lazy[N], siz[N];inline void push_up(int x) {fnt[x] = bak[x] = ans[x];if(ls) fnt[x] = fnt[ls] + fnt[x], bak[x] = bak[x] + bak[ls];if(rs) fnt[x] = fnt[x] + fnt[rs], bak[x] = bak[rs] + bak[x];}inline void push(int x) { swap(ls, rs), swap(fnt[x], bak[x]), tag[x] ^= 1; }inline void push_down(int x) {if(tag[x]) {if(ls) push(ls);if(rs) push(rs);tag[x] = 0;}}#define get(x) (ch[f[x]][1] == x)                        // 查询节点X是父亲的哪个儿子#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x) // 判断X是否是所在树的根inline void rotate(int x) { // 将X向上旋转一层int y = f[x], z = f[y], k = get(x);if(!isRoot(y)) ch[z][ch[z][1] == y] = x;ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;ch[x][!k] = y, f[y] = x, f[x] = z;push_up(y); push_up(x);}inline void update(int x) { // X所在路径自上向下释放Lazy标记if(!isRoot(x)) update(f[x]);push_down(x);}inline void splay(int x) { // 将节点X旋至当前所在平衡树的树根(带LCT性质认子不认父)update(x);for(int fa = f[x]; !isRoot(x); rotate(x), fa = f[x]){if(!isRoot(fa)) rotate(get(fa) == get(x) ? fa : x);}push_up(x);}int access(int x) { // 把从根到X的所有点放在一条实链里，使根到X成为一条实路径int p;for(p = 0; x; x = f[p = x]) splay(x), ch[x][1] = p, push_up(x);return p;}void makeRoot(int p) { access(p), splay(p), push(p); } // 使X点成为其所在树的根int findRoot(int x) { // 找到X所在树的根节点编号access(x), splay(x);while(ch[x][0]) push_down(x), x = ch[x][0];splay(x);return x;}void link(int x, int y) { // 在x,y之间连边makeRoot(x);  f[x] = y;}void split(int x, int y) { // 提取出x,y之间的路径makeRoot(x);access(y), splay(y);}
}int n, m, k;int get_ans(int val0, int val1, int z) {int ans = 0;for(long long i = 63; i >= 0; --i) {if(val0 >> i & 1ull) ans += 1ull << i;else if(val1 >> i & 1ull && (1ull << i) <= z) ans += 1ull << i, z -= 1ull << i;}return ans;
}inline void solve() {cin >> n >> m >> k;for(int i = 1; i <= n; i++) {ull x, op; cin >> op >> x;LCT::ans[i].assign(op, x);}for(int i = 1; i < n; i++) {int u, v; cin >> u >> v;LCT::link(u, v);}   for(int i = 1; i <= m; i++) {ull op, x, y, z; cin >> op >> x >> y >> z;if(op == 1) {LCT::split(x, y);// cout << "#dng : " << LCT::fnt[y].ans0 << " " << LCT::fnt[y].ans1 << endl;cout << get_ans(LCT::fnt[y].ans0, LCT::fnt[y].ans1, z) << endl;} else {LCT::ans[x].assign(y, z);LCT::splay(x);}}
}signed main() {ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; // cin >> t;while(t--) solve();return 0;
}