字典树使用二维 vector 的话 C++17 会 MLE,二维 int 数组或 vector<array<int, 2>> 都没问题,想问下可以用二维 vector 的方式过吗
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10;
vector nxt(N << 5, vector<int>(2));
struct Trie {
// int nxt[N << 5][2];
int cnt = 0;
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int c = (x >> i) & 1;
if (nxt[p][c] == 0) {
nxt[p][c] = ++cnt;
}
p = nxt[p][c];
}
}
int get(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int c = (x >> i) & 1;
if (nxt[p][c ^ 1]) {
p = nxt[p][c ^ 1];
res |= 1 << i;
} else {
p = nxt[p][c];
}
}
return res;
}
} T;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<pair<int, int>>> G(n);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
int ans = 0;
vector<int> xor_sum(n);
function<void(int, int)> dfs = [&](int u, int p) {
T.insert(xor_sum[u]);
ans = max(ans, T.get(xor_sum[u]));
for (auto [v, w] : G[u]) {
if (v == p) {
continue;
}
xor_sum[v] = xor_sum[u] ^ w;
dfs(v, u);
}
};
dfs(0, -1);
cout << ans << "\n";
return 0;
}