洛谷 P4551 最长异或路径 & 【模板】01字典树

传送门

以这个做模板还是很纠结的……

解题思路

01字典树，就是一个二叉的字典树，把许多数字二进制拆分，然后扔进字典树里，就可以进行许多骚操作。

回到这个题，朴素算法为预处理出每个点到根节点的路径的异或和，然后枚举任意两个点，把两个节点到根节点的异或和异或起来即为答案。原因是lca到根节点之间的路径异或两遍等于没有异或（a^a=0)。

因为按位异或不会牵扯到进位问题，所以可以用贪心思想。

还是预处理出每个节点到根节点的路径的异或和，然后把它们扔到字典树中，

这里扔的时候一定要从高位扔，因为最高位能取1是一定要取1。

这样枚举每个节点，然后跑字典树找出以这个节点为一个端点的最长异或路径值。

时间复杂度为O(nlogm)，n为枚举的节点数，logm为字典树深度。

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=100005;
 6 int n,er[35],ans,cnt,p[maxn],ch[maxn*30][2],num=1,a[maxn];
 7 struct node{
 8     int v,next,value;
 9 }e[maxn*2];
10 void insert(int u,int v,int w){
11     cnt++;
12     e[cnt].v=v;
13     e[cnt].next=p[u];
14     e[cnt].value=w;
15     p[u]=cnt;
16 }
17 void update(int w){
18     int res=1;
19     for(int i=30;i>=0;i--){
20         if(!ch[res][(w>>i)&1]) res=ch[res][(w>>i)&1]=++num;
21         else res=ch[res][(w>>i)&1];
22     }
23 }
24 void dfs(int u,int fa,int w){
25     a[u]=w;
26     ans=max(ans,a[u]);
27     update(w);
28     for(int i=p[u];i!=-1;i=e[i].next){
29         if(e[i].v==fa) continue;
30         dfs(e[i].v,u,w^e[i].value);
31     }
32 }
33 int query(int w){
34     int res=1,ans=0;
35     for(int i=30;i>=0;i--){
36         if(ch[res][((w>>i)&1)^1]){
37             res=ch[res][((w>>i)&1)^1];
38             ans|=er[i];
39         }else{
40             res=ch[res][(w>>i)&1];
41         }
42     }
43     return ans;
44 }
45 void dfs2(int u,int fa){
46     ans=max(ans,query(a[u]));
47     for(int i=p[u];i!=-1;i=e[i].next){
48         if(e[i].v==fa) continue;
49         dfs2(e[i].v,u);
50     }
51 }
52 int main(){
53     memset(p,-1,sizeof(p));
54     er[0]=1;
55     for(int i=1;i<=30;i++) er[i]=er[i-1]*2;
56     cin>>n;
57     for(int i=1;i<n;i++){
58         int u,v,w;
59         scanf("%d%d%d",&u,&v,&w);
60         insert(u,v,w);
61         insert(v,u,w);
62     }
63     dfs(1,-1,0);
64     dfs2(1,-1);
65     cout<<ans;
66     return 0;
67 }