郑州网站建设联系方式,东莞个人网站设计,无锡机关单位建设网站,首页界面设计题目给一棵有边权的树#xff0c;问树上任意两点路径上的边异或值最多是多少。 记录每个点u到根路径的异或值xor[u]#xff0c;那么任意两点u、v路径的异或值就是xor[u]^xor[v]。 于是这个问题就变成了从n个数中任取两个数异或#xff0c;求最大异或值#xff0c;这是个经典…题目给一棵有边权的树问树上任意两点路径上的边异或值最多是多少。 记录每个点u到根路径的异或值xor[u]那么任意两点u、v路径的异或值就是xor[u]^xor[v]。 于是这个问题就变成了从n个数中任取两个数异或求最大异或值这是个经典的问题用字典树解决。 方法就是所有数的二进制形式构建成一棵01字典树枚举每个数从字典树中就能找到对应的最大的答案。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 #define MAXN 1100006 struct Edge{7 int v,w,next;8 }edge[MAXN1];9 int NE,head[MAXN];
10 void addEdge(int u,int v,int w){
11 edge[NE].vv; edge[NE].ww; edge[NE].nexthead[u];
12 head[u]NE;
13 }
14 int tn,ch[3300000][2];
15 void insert(int a){
16 int x0;
17 for(int i31; i0; --i){
18 int y(ai)1;
19 if(ch[x][y]0) ch[x][y]tn;
20 xch[x][y];
21 }
22 }
23 int query(int a){
24 int x0,res0;
25 for(int i31; i0; --i){
26 int y((ai)1)^1;
27 if(ch[x][y]) xch[x][y],res|1i;
28 else xch[x][y^1];
29 }
30 return res;
31 }
32 int val[MAXN];
33 void dfs(int u,int w,int fa){
34 val[u]w;
35 insert(w);
36 for(int ihead[u]; i!-1; iedge[i].next){
37 int vedge[i].v;
38 if(vfa) continue;
39 dfs(v,w^edge[i].w,u);
40 }
41 }
42 int main(){
43 int n,a,b,c;
44 while(~scanf(%d,n)){
45 NE0;
46 memset(head,-1,sizeof(head));
47 for(int i1; in; i){
48 scanf(%d%d%d,a,b,c);
49 addEdge(a,b,c); addEdge(b,a,c);
50 }
51 tn0;
52 memset(ch,0,sizeof(ch));
53 dfs(0,0,0);
54 int res0;
55 for(int i0; in; i){
56 resmax(res,query(val[i]));
57 }
58 printf(%d\n,res);
59 }
60 return 0;
61 } 转载于:https://www.cnblogs.com/WABoss/p/5171265.html
