如果对每一个点的儿子的权值建立trie树 空间复杂度应该是能承受的住的啊。

/*-----input blog start------//
<!-- more -->
//-----input blog end  ------*/
/*!
 * Copyright(c) 2019 Shu_Yan
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/shuyumo2003/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool written by Shu_Yu_Mo(Shu_Yan).
 * date: 2020-07-07 22:52:48
 * pid : P6018
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<climits>
#include<algorithm>
#include<ctime>
#define For(x) for(int i = 1;i <= x;i++)
#define _For(x) for(int i = 0;i < x;i++)
#define LL long long
#define MOD 998244353
#define show(x) cerr <<"[" <<  __LINE__ << "] " << #x << " = " << x << endl;
using namespace std;
// const int _ = 1e6 + 10;
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; } 
//--------------init finish line-------------------

const int _ = 5e3 + 10;
int head[_];
struct edges{
    int node;
    int nxt;
}edge[_];
int tot = 0;
void add(int u, int v){
    edge[++tot].nxt = head[u];
    head[u] = tot;
    edge[tot].node = v;
}
int fa[_];
struct trie{
    struct node{
        node *ch[2];
        short   tfw;
        short   v;
        void maintain(){
            int k1 = 0, k2 = 0;
            if(ch[0]) k1 = (ch[0]->v << 1) | 0;
            if(ch[1]) k2 = (ch[1]->v << 1) | (ch[1]->tfw&1);
            v = k1 ^ k2;
        }
        node (){ v  = 0;ch[0] = ch[1] = NULL; tfw = 0; }
        ~node(){ if(ch[0]) delete ch[0]; if(ch[1]) delete ch[1]; }
    };
    int dp;
    node *rt;
    void insert(int x){ insert(rt, x); }
    void insert(node *o, int val){
        if(val == 0) return ;
        int ck = val&1;
        if(!o->ch[ck]) o->ch[ck] = new node();
        o->ch[ck]->tfw ++;
        insert(o->ch[ck], val >> 1);
        o->maintain();
    }
    void erase(int val){ erase(rt, val); }
    void erase(node *o, int val){
        if(val == 0) return ;
        int ck = val&1;
        o->ch[ck]->tfw --;
        erase(o->ch[ck], val >> 1);
        o->maintain();
        if(o->ch[0]->tfw <= 0) { delete o->ch[0]; o->ch[0] = NULL; }
        if(o->ch[1]->tfw <= 0) { delete o->ch[1]; o->ch[1] = NULL; }
    }
//    void marge(trie &o){
//    	marge(rt, o.rt);
//	}
//	node*  marge(node *a, node *b){
//		if(!a) return b;
//		if(!b) return a;
//		a->tfw += b->tfw;
//		a->ch[0] = marge(a->ch[0], b->ch[0]);
//		a->ch[1] = marge(a->ch[1], b->ch[1]);
//		a->maintain();
//	}
	void addall(){ addall(rt); }
	void addall(node *o){
		swap(o->ch[0], o->ch[1]);
		if(o->ch[0]) addall(o->ch[0]);
		else if(!o->ch[1]) o->ch[1] = new node(), o->ch[1]->tfw = o->tfw;//, printf("add one %d\n", o->tfw); 
		o->maintain();
	}
    trie(){ rt = new node(); }
}t[_];
int tar[_];
int v[_];
int n, m;
int rt;
void dfs0(int o, int f){
	fa[o] = f;
	for(int i = head[o];i;i = edge[i].nxt){
		int node = edge[i].node;
		
		if(node != f) t[o].insert(v[node]);
		if(node != f) dfs0(node, o);
	}
}
inline int get(int x){ if(x == 0) return 0; return v[x] + x != rt ? tar[fa[x]] : 0; }
int main()
{
#ifdef LOCAL_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    clock_t c1 = clock();
    
    
//    cerr << int(5e5) * 64 * 4 / 1024 / 1024 << endl;
    
    n = read(), m = read(), rt = 0;
    for(int i = 1;i < n;i++){
    	int u = read(), v = read();
    	add(u, v);add(v, rt = u);
	}
	for(int i = 1;i <= n;i++) v[i] = read();
	dfs0(rt, 0);
    while(m--){
    	int opt = read();
    	if(opt == 1) {
    		int x = read();
    		t[x].addall();
    		v[fa[x]] ++;
    		tar[x] ++;
		} else if(opt == 2){
			int x = read(), val = read();
			int _v = get(x);
			t[fa[x]].erase(_v);
			t[fa[x]].insert(_v - val);
			v[x] -= val;
		} else {
			int x = read();
			int res = t[x].rt->v;
			res ^= get(fa[x]);
			printf("%d\n", res);
		}
	}
//	while(true) ;
    
    
    
    std::cerr << "\n\nTime:  " << clock() - c1 << "  ms" << std::endl;
	return 0;
}