任何新类型的题，都可以转换成自己熟悉的题来解答。
就像下面的这题：
给定一个树，树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或和：
⊕ 为异或符号。
给定上述的具有n个节点的树，你能找到异或长度最大的路径吗？
输入格式
第一行包含整数n，表示树的节点数目。
接下来n-1行，每行包括三个整数u，v，w，表示节点u和节点v之间有一条边权重为w。
输出格式
输出一个整数，表示异或长度最大的路径的最大异或和。
数据范围
1≤n≤100000<?XML:NAMESPACE PREFIX = "[default] http://www.w3.org/1998/Math/MathML" NS = "http://www.w3.org/1998/Math/MathML" />1≤n≤100000,
0≤u,v<n0≤u,v<n,
0≤w<2310≤w<231
输入样例：
4
0 1 3
1 2 4
1 3 6输出样例：
7样例解释
样例中最长异或值路径应为0->1->2,值为7 (=3 ⊕ 4)
此题思路：
首先，这里时求树中的任意两节点间的异或长度最大值，但是我们可以求出根节点到各个节点的异或和，这里假设D[x]表示根到x的边权所有的异或值则有
D[x] = D[father[x]] xor weight(x,fahter[x])
这里的weight(x, father[x])表示的x到它父亲边的权值。
因此，我们转换思路先求出每个节点到根的异或值，然后用D[i]保存。问题就变成了，给出一段数据，求最大异或和。
这里提示一下：
D[x] xor D[y]就是这条路径的异或长度，因为其中重复的路径已经通过异或的性质减去。
所以通过字典树求出答案，和上一题的，最大异或和https://www.acwing.com/problem/content/145/
差不多。
代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5
6 const int N = 1e5 + 5, M = 3e6;
7 int h[N], e[N*2], c[N*2], ne[N*2], cnt, n;
8 int trie[M][2], tot;
9 int d[N];
10 void add(int u, int v, int w){
11 e[cnt] = v, c[cnt] = w, ne[cnt] = h[u], h[u] = cnt ++;//邻接表存储树
12 }
13
14 void dfs(int u, int father, int sum){
15 d[u] = sum;
16 for(int i = h[u]; ~i; i = ne[i]){
17 int j = e[i];
18 if(j != father)
19 dfs(j, u, sum^c[i]);
20 }
21 }
22
23 void insert(int x) {
24 int p = 0;
25 for(int i = 30; ~i; -- i) {
26 int &s = trie[p][x >> i & 1];
27 if(!s) s = ++tot;
28 p = s;
29 }
30 }
31
32 int query(int x) {
33 int p = 0, res = 0;
34 for(int i = 30; i >= 0; -- i){
35 int s = x >> i & 1;
36 if(trie[p][!s]){
37 p = trie[p][!s];
38 res += 1 << i;
39 }
40 else p = trie[p][s];
41 }
42 return res;
43 }
44
45 int main() {
46 cin >> n;
47 memset(h, -1, sizeof(h));
48 for(int i = 0; i < n-1; ++ i) {
49 int u, v, w;
50 cin >> u >> v >> w;
51 add(u, v, w);
52 add(v, u, w);
53 }
54 dfs(0, -1, 0);
55 for(int i = 0; i < n; ++ i)
56 insert(d[i]);
57
58 int res = 0;
59 for(int i = 0; i < n; ++ i)
60 res = max(res, query(d[i]));
61 cout << res << endl;
62 return 0;
63 }
64
65