题目链接：https://www.acwing.com/problem/content/description/146/

思路：考虑 固定1为根  有节点a,b a到1的路径之间的异或值和b到1之间的异或值相异或的话

得到的结果就是a到b路径的异或值 画图就可以理解 所以题目可以转换成用dfs求出

根1到所有节点的异或值a[i] 然后求这些a[i]中 某两个组合的最大值 就变成01trie的模板题了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair<int,int>
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 
12 
13 int a[maxn];
14 vector<pi>E[maxn];
15 
16 void dfs(int u,int fa)
17 {
18     for(auto &v:E[u])
19     {
20         if(v.fi==fa) continue;
21         a[v.fi]=a[u]^v.sc;
22         dfs(v.fi,u);
23     }
24 }
25 
26 int trie[maxn*32][2];
27 int tot;
28 
29 
30 void add(int x)
31 {
32     int p=0;
33     for(int i=30;i>=0;i--)
34     {
35         int u=(x>>i)&1;
36         if(!trie[p][u]) trie[p][u]=++tot;
37         p=trie[p][u];
38     }
39 }
40 
41 int query(int x)
42 {
43     int ans=0;
44     int p=0;
45     for(int i=30;i>=0;i--)
46     {
47         int u=(x>>i)&1;
48         if(trie[p][!u])
49         {
50             ans<<=1;
51             ans+=!u;
52             p=trie[p][!u];
53         }
54         else
55         {
56             ans<<=1;
57             ans+=u;
58             p=trie[p][u];
59         }
60     }
61     return ans;
62 }
63 
64 
65 
66 int main()
67 {
68     ios::sync_with_stdio(false);
69     cin.tie(0);
70     int n;
71     cin>>n;
72     for(int i=1;i<n;i++)
73     {
74         int x,y,z;
75         cin>>x>>y>>z;
76         x++;y++;
77         E[x].pb({y,z});
78         E[y].pb({x,z});
79     }
80     dfs(1,0);
81     for(int i=1;i<=n;i++) add(a[i]);
82     int ans=0;
83     for(int i=1;i<=n;i++)
84     {
85         int t=query(a[i]);
86         ans=max(ans,t^a[i]);
87     }
88     cout<<ans<<'\n';
89 
90 
91 
92 }

View Code