洛谷P4551 最长异或路径（字典树，异或）

题目链接

https://www.luogu.com.cn/problem/P4551

思路

因为一个数同时对异或两个相同的数，其值不变。

因此我们很容易发现，对于节点$u$与节点$v$路径上的异或和可以表示为从根节点到$u$的异或和异或上根节点到$v$的异或和。

因此我们可以对根节点到每一个节点的异或和按照二进制的形式插入到$Trie$树上，最后贪心求得最终的答案即可。

时间复杂度：$O(30n)$

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n;
vector<int>v;
vector<pair<int, int>>mp[N];
struct Trie
{const int static maxn = 3e6 + 5;int son[maxn][2], idx;void insert(int x){int p = 0;for (int i = 30; i >= 0; i--){int &s = son[p][(x >> i) & 1];if (!s) s = ++idx;p = s;}}int query(int x){int res = 0, p = 0;for (int i = 30; i >= 0; i--){int bit = (x >> i) & 1;if (son[p][!bit]){res += (1ll << i);p = son[p][!bit];}else p = son[p][bit];}return res;}
} trie;
void dfs(int u, int fu, int sum)
{v.push_back(sum);for (int i = 0; i < mp[u].size(); i++){int j = mp[u][i].first;int w = mp[u][i].second;if (j == fu) continue;dfs(j, u, sum ^ w);}
}
void solve()
{cin >> n;for (int i = 1, u, v, w; i < n; i++){cin >> u >> v >> w;mp[u].push_back({v, w});mp[v].push_back({u, w});}dfs(1, -1, 0);for (int val : v){trie.insert(val);}int ans = 0;for (int val : v){ans = max(ans, trie.query(val));}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}