题解

Difficulty：4.2 / Easy

Tag：01 Trie

不知道为啥，忘了写了。

看的时候把 $v$ 和 $x$ 交换一下。懒得改了。

首先考虑不带修。

显然连成的环就是 $x\to y$ 的树链加上给的边。注意到这个可以转化成 $(1\to x)\oplus (1\to y)$。所以我们只需要开个 01 Trie 查询 $(1\to y)\oplus (1\to x) \oplus v$ 的最大值即可。注意不能自环，所以查询时必须删掉 $1\to x$。

然后考虑带修。

开个全局变量 $p$，记录修改的异或和。

显然就会变成偶数条边不变，奇数条边额外异或 $p$。

所以我们可以对树进行二分图染色，分颜色讨论。

做完了。

namespace cjdst{
	const int N = 200000, M = 30;
	std::vector <pii> v[N + 5];
	int n, m;
	int val[N + 5];
	int siz[N * M + 5];
	int son[N * M + 5][2];
	int color[N + 5];
	int ctnode, root[2], curxor;
	void insert(int &u, int dep, int val){
		if(!u) u = (++ctnode);
		if(dep < 0){
			siz[u]++;
			return;
		}
		insert(son[u][val >> dep & 1], dep - 1, val);
		siz[u] = siz[son[u][0]] + siz[son[u][1]];
	}
	void del(int &u, int dep, int val){
		if(dep < 0){
			siz[u]--;
			return;
		}
		del(son[u][val >> dep & 1], dep - 1, val);
		siz[u] = siz[son[u][0]] + siz[son[u][1]];
	}
	int query(int u, int dep, int val){
		if(dep < 0) return 0;
		if(siz[son[u][~val >> dep & 1]]){
			return query(son[u][~val >> dep & 1], dep - 1, val) | (1 << dep);
		}
		return query(son[u][val >> dep & 1], dep - 1, val);
	}
	
	void dfs(int cur, int fa){
		color[cur] = color[fa] ^ 1;
		insert(root[color[cur]], M, val[cur]);
		for(auto i:v[cur]){
			if(i.first == fa) continue;
			val[i.first] = val[cur] ^ i.second;
			dfs(i.first, cur);
		}
	}
	
	void solve(){
		std::cin >> n >> m;
		for(int i = 1; i < n; i++){
			int x, y, z;
			std::cin >> x >> y >> z;
			v[x].push_back({y, z});
			v[y].push_back({x, z});
		}
		dfs(1, 0);
		while(m--){
			char c;
			std::cin >> c;
			if(c == '^'){
				int val;
				std::cin >> val;
				curxor ^= val;
			}else{
				int x, y;
				std::cin >> x >> y;
				del(root[color[x]], M, val[x]);
				std::cout << std::max(query(root[color[x]], M, val[x] ^ y), query(root[color[x] ^ 1], M, val[x] ^ y ^ curxor)) << ' ';
				insert(root[color[x]], M, val[x]);
			}
		}
		std::cout << '\n';
		for(int i = 1; i <= ctnode; i++){
			siz[i] = 0;
			son[i][0] = son[i][1] = 0;
		}
		root[0] = root[1] = ctnode = curxor = 0;
		for(int i = 1; i <= n; i++){
			v[i].clear();
		}
	}
}

时间复杂度：$O(n\log V)$。