该题是的树上加修改版

先说说《起床困难综合征》，由于不同位运算之间不满足交换律，故必须按顺序执行操作

考虑位运算套路 —— 拆位，对于未知的初始值，它的每一位也是未知的，所以可以用两个变量 $a_0, a_1$ 来当作初始值当前位为 $0$ 或 $1$ 时最终可以得到的值，最后贪心即可

附上部分代码：

1 int a1 = 0, a2 = - 1; 2 for (int i = 1; i <= N; i ++) { 3     scanf ("%s", opt + 1); 4     int p = getnum (); 5     if (opt[1] == 'A') 6         a1 &= p, a2 &= p; 7     else if (opt[1] == 'O') 8         a1 |= p, a2 |= p; 9     else if (opt[1] == 'X')10         a1 ^= p, a2 ^= p;11 }12 int ps = 0, ans = 0;13 for (int j = 30; j >= 1; j --) {14     if (a1 & (1 << (j - 1)))15         ans += (1 << (j - 1));16     else if ((a2 & (1 << (j - 1))) && ps + (1 << (j - 1)) <= M)17         ans += (1 << (j - 1)), ps += (1 << (j - 1));18 }

那么现在将操作扩展到树上，使用 $LCT$ 来维护其代表的链的 $a_0, a_1$ ，通过找规律可以发现：

设新的 $a_0, a_1$ 分别为 $f_0, f_1$ ，旧的分别为 $x.a_0, x.a_1$ 及 $y.a_0, y.a_1$ （其中 $x, y$ 为从左往右），现在要合并 $x, y$

对于 $f_0$ 很好想到要将 $x.a_0 \ opt \ y.a_0$ 与 $x.a_0 \ opt \ y.a_1$ 合并即可得解，公式即为 $(x.a_0 \& y.a_1) | (~ x.a_0 \& y.a_0)$ ，其中， $(x.a_0 \& y.a_t)$ 为通解，第二个的取反即为消去 $x.a_0$ 中为 $1$ 的位对第二个操作的影响

$pushup$ 写完就是 $LCT$ 常规操作了，求答案也是贪心即可

注意：由于有 $makeroot$ 操作，又求答案顺序一定是从左往右，所以还需要维护一下从右往左的答案，用于在 $reverse$ 的时候交换

代码

1 #include 
     
        2 #include 
      
         3 #include 
       
          4   5 using namespace std;  6   7 typedef long long LL;  8 typedef unsigned long long uLL;  9  10 const int MAXN = 1e05 + 10; 11  12 // {&, |, ^} -> {1, 2, 3} 13 int opt[MAXN]= {
   0}; 14 LL value[MAXN]= {
   0}; 15  16 struct optionSt { 17     LL a0, a1; 18  19     optionSt () {} 20     optionSt (LL fa0, LL fa1) : 21         a0 (fa0), a1 (fa1) {} 22  23 } ; 24 optionSt merge (optionSt x, optionSt y) { 25     LL f0 = ((x.a0 & y.a1) | (~ x.a0 & y.a0)); 26     LL f1 = ((x.a1 & y.a1) | (~ x.a1 & y.a0)); 27     return optionSt (f0, f1); 28 } 29 /*pair
        
          merge (pair
         
           p1, pair
          
            p2) { 30 LL a00 = p1.first, a10 = p1.second; 31 LL a01 = p2.first, a11 = p2.second; 32 LL a0 = ((a00 & a11) | (~ a00 & a01)); 33 LL a1 = ((a10 & a11) | (~ a10 & a01)); 34 return make_pair (a0, a1); 35 }*/ 36 optionSt calc (int op, LL val) { 37 switch (op) { 38 case 1: 39 return optionSt (0ll, val); 40 case 2: 41 return optionSt (val, - 1ll); 42 case 3: 43 return optionSt (val, ~ val); 44 } 45 } 46 47 int father[MAXN]= { 0}; 48 int son[MAXN][2]= { 0}; 49 optionSt tval[MAXN], froml[MAXN], fromr[MAXN]; 50 int revtag[MAXN]= { 0}; 51 52 int isroot (int p) { 53 return son[father[p]][0] != p && son[father[p]][1] != p; 54 } 55 int sonbel (int p) { 56 return son[father[p]][1] == p; 57 } 58 void reverse (int p) { 59 if (! p) 60 return ; 61 swap (son[p][0], son[p][1]); 62 swap (froml[p], fromr[p]); // 注意要更改左右顺序 63 revtag[p] ^= 1; 64 } 65 void pushup (int p) { 66 froml[p] = fromr[p] = tval[p]; 67 if (son[p][0]) { 68 froml[p] = merge (froml[son[p][0]], froml[p]); 69 fromr[p] = merge (fromr[p], fromr[son[p][0]]); 70 } 71 if (son[p][1]) { 72 froml[p] = merge (froml[p], froml[son[p][1]]); 73 fromr[p] = merge (fromr[son[p][1]], fromr[p]); 74 } 75 } 76 void pushdown (int p) { 77 if (revtag[p]) { 78 reverse (son[p][0]), reverse (son[p][1]); 79 revtag[p] = 0; 80 } 81 } 82 void rotate (int p) { 83 int fa = father[p], anc = father[fa]; 84 int s = sonbel (p); 85 son[fa][s] = son[p][s ^ 1]; 86 if (son[fa][s]) 87 father[son[fa][s]] = fa; 88 if (! isroot (fa)) 89 son[anc][sonbel (fa)] = p; 90 father[p] = anc; 91 son[p][s ^ 1] = fa, father[fa] = p; 92 pushup (fa), pushup (p); 93 } 94 int Stack[MAXN]; 95 int top = 0; 96 void splay (int p) { 97 top = 0, Stack[++ top] = p; 98 for (int nd = p; ! isroot (nd); nd = father[nd]) 99 Stack[++ top] = father[nd];100 while (top > 0)101 pushdown (Stack[top]), top --;102 for (int fa = father[p]; ! isroot (p); rotate (p), fa = father[p])103 if (! isroot (fa))104 sonbel (p) == sonbel (fa) ? rotate (fa) : rotate (p);105 pushup (p);106 }107 void Access (int p) {108 for (int tp = 0; p; tp = p, p = father[p])109 splay (p), son[p][1] = tp, pushup (p);110 }111 void Makeroot (int p) {112 Access (p), splay (p), reverse (p);113 }114 void Split (int x, int y) {115 Makeroot (x);116 Access (y), splay (y);117 }118 void link (int x, int y) {119 Makeroot (x);120 father[x] = y;121 }122 123 int N, M, K;124 125 uLL Query (int x, int y, LL lim) {126 Split (x, y);127 uLL ans = 0, ps = 0;128 LL a0 = froml[y].a0, a1 = froml[y].a1;129 for (int j = K; j >= 1; j --) {130 if (a0 & (1ll << (j - 1)))131 ans += (1ll << (j - 1));132 else if ((a1 & (1ll << (j - 1))) && ps + (1ll << (j - 1)) <= lim)133 ans += (1ll << (j - 1)), ps += (1ll << (j - 1));134 }135 return ans;136 }137 138 int getint () {139 int num = 0;140 char ch = getchar ();141 142 while (! isdigit (ch))143 ch = getchar ();144 while (isdigit (ch))145 num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();146 147 return num;148 }149 LL getLL () {150 LL num = 0;151 char ch = getchar ();152 153 while (! isdigit (ch))154 ch = getchar ();155 while (isdigit (ch))156 num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();157 158 return num;159 }160 uLL getuLL () {161 uLL num = 0;162 char ch = getchar ();163 164 while (! isdigit (ch))165 ch = getchar ();166 while (isdigit (ch))167 num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();168 169 return num;170 }171 void work (uLL x) {172 if (x >= 10)173 work (x / 10);174 putchar (x % 10 + '0');175 }176 void println (uLL x) {177 work (x), puts ("");178 }179 180 int main () {181 N = getint (), M = getint (), K = getint ();182 for (int i = 1; i <= N; i ++) {183 opt[i] = getint (), value[i] = getLL ();184 tval[i] = calc (opt[i], value[i]);185 }186 for (int i = 1; i < N; i ++) {187 int u = getint (), v = getint ();188 link (u, v);189 }190 for (int Case = 1; Case <= M; Case ++) {191 int op = getint ();192 if (op == 1) {193 int x = getint (), y = getint ();194 uLL lim = getLL ();195 println (Query (x, y, lim));196 }197 else if (op == 2) {198 int p = getint (), nopt = getint ();199 LL delta = getLL ();200 Access (p), splay (p);201 opt[p] = nopt, value[p] = delta;202 tval[p] = calc (opt[p], value[p]);203 pushup (p);204 }205 }206 207 return 0;208 }209 210 /*211 5 5 3212 1 7213 2 6214 3 7215 3 6216 3 1217 1 2218 2 3219 3 4220 1 5221 1 1 4 7222 1 1 3 5223 2 1 1 3224 2 3 3 3225 1 1 3 2226 */227 228 /*229 2 2 2230 2 2231 2 2232 1 2233 2 2 2 2234 1 2 2 2235 */