RT

P4551 最长异或路径

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
 
using namespace std;

vector<int> tree[(int)1e5 + 10], val[(int)1e5 + 10];
int n, u, v, w, d[(int)1e5 + 10], trie[(int)1e5 * 32 + 10][2], idx, ans = -0x3f3f3f3f, b[(int)1e5 + 10];

void dfs(int x) {
	for (int i = 0; i < tree[x].size(); i ++) {
		if (!b[tree[x][i]]) {
			b[tree[x][i]] = 1;
			d[tree[x][i]] = d[x] ^ val[x][i];
			dfs(tree[x][i]);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n - 1; i ++) {
		cin >> u >> v >> w;
		tree[u].push_back(v);
		tree[v].push_back(u);
		val[u].push_back(w);
		val[v].push_back(w);
	}
	dfs(v);// 换成u就会 PAC
	for (int i = 0; i < n; i ++) {
		int p = 0, ans2 = 0;
		for (int k = 31; k >= 0; k --) {
			int ch = d[i] >> k & 1;
			if (trie[p][ch] == 0) trie[p][ch] = ++ idx;
			p = trie[p][ch];
		}
		p = 0;
		for (int k = 31; k >= 0; k --) {
			int ch = d[i] >> k & 1;
			if (trie[p][ch ^ 1]) p = trie[p][ch ^ 1], ans2 |= 1 << k;
			else p = trie[p][ch];
		}
		ans = max(ans, ans2);
	}
	cout << ans << '\n';
	return 0;
}

有没有大佬帮蒟蒻解释一下？