3764树上的异或值（自己研究的静态字典树）

题意：
      给一颗树，最多10W个点，然后每条边上都有一个权值，任意两点的权值是他们经过的边的异或值，问最大的权值是多少？（任意两点中最大的）


思路：

      首先突破口是要想到a^b=c^a ^c^b,那么任意两点的异或值就可以是他们到根节点的异或然后异或一下，so先把所有点到根节点的异或值求出来，这个好求，然后就是相当于给你n个值，让你在里面选择两个值异或起来最大，这个也是比较有意思的（之前做过这个问题），我们直接把所有数字都弄成31位的二进制数，高位在前面，这样就得到了n个31位的字符串，然后把他们全都加到字典树里，加完后在开始查询，贪心的去查，因为先遇到的是高位，所以可以简单顺序贪心，细节不说了，自己想想，很容易想出来。还有就是这个题目一开始我用的动态字典树，结果超时了，看到有人说得用静态字典树，没写过静态的，就自己尝试着写了个类似线段树的字典树，结果爆内存了，然后我就想，动态字典树超时的原因就是在malloc这个地方呗，那我就实现开好一堆结构体，等到改分配内存的时候就从里面拿出来一个给字典树就行了，结果交上去就直接AC了，虽然还没写过静态的字典树，也不知道哪个该怎么写，不过感觉事先开好，然后分配的时候id+1拿出来也能解决动态的超时问题，以后超时就这样写吧，但是有一点，这个数组要开多大这个不好算，所以为了安全起见尽可能的大就行了。

#include<stdio.h> #include<stdlib.h> #include<string.h>#define N_node 100005 #define N_edge 200010typedef struct {int to ,next,cost; }STAR;typedef struct Tree {Tree *next[2]; }Tree;STAR E[N_edge]; int list[N_node] ,tot; int XOR[N_node]; int mark[N_node]; char str[N_node][35]; Tree T[N_node * 50]; int nowT; Tree root;void add(int a ,int b ,long long c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot; }void DFS(int x ,long long nowxor) {mark[x] = 1;XOR[x] = nowxor;for(int k = list[x] ;k ;k = E[k].next){if(!mark[E[k].to])DFS(E[k].to ,nowxor^E[k].cost);}return ; }void BuidTree(char *str) {Tree *p = &root ,*q;for(int i = 0 ;i <= 30 ;i ++){int id = str[i];if(p -> next[id] == NULL){q = &T[++nowT];q -> next[0] = q -> next[1] = NULL;p -> next[id] = q;p = p -> next[id];}else p = p -> next[id];} }int Query(char *str) {Tree *p = &root;int ans = 0;for(int i = 0 ;i <= 30 ;i ++){int id = str[i] ^ 1;if(p -> next[id] == NULL) p = p -> next[id^1];else{p = p -> next[id];ans += (1 << (30 - i));}}return ans; }int main () {int n ,a ,b ,c ,i ,j;while(~scanf("%d" ,&n)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i < n ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);add(a + 1 ,b + 1 ,c);add(b + 1 ,a + 1 ,c);}memset(mark ,0 ,sizeof(mark));DFS(1 ,0);root.next[0] = root.next[1] = NULL;nowT = 0;for(i = 1 ;i <= n ;i ++){for(j = 0 ;j <= 30 ;j ++){str[i][j] = (((1 << (30 - j)) & XOR[i]) != 0);}BuidTree(str[i]);}int max = 0;for(i = 1 ;i <= n ;i ++){int tmp = Query(str[i]);if(max < tmp) max = tmp;}printf("%d\n" ,max);}return 0; }

总结

以上是生活随笔为你收集整理的3764树上的异或值（自己研究的静态字典树）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。