poj 3764 The xor-longest Path 字典树 + 前缀和-白红宇的个人博客

发布日期：2021-09-25 23:57:56 浏览次数：9 分类：技术文章

本文共 1198 字，大约阅读时间需要 3 分钟。

题意：在一棵树上选择一个路径，使路径权值异或之和最大。

既然是在字典树专题里的，自然也就想到了字典树，不过只能求两个数的最大异或，而这个题不确定是不是两个数，而且路径也很难找出来，这个时候想起来之前学主席树做 “最大异或和” 这道模板题的时候，将区间异或转换成了前缀异或，茅塞顿开，发现可以用dfs处理前缀和，让后每一条路径不就是两个前缀异或起来嘛。这样就转换成了两个数的异或，可以用字典树轻松解决。

我不会算字典树的空间，每个题基本都得re一次，开的可能有点大。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,M=200020,S=50,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int e[M],ne[M],w[M],h[N],idx;int tr[N*S][2],tot;vector
                
                 v;void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}void insert(int x){ int p=0; for(int i=30;i>=0;i--) { int u=x>>i&1; if(!tr[p][u]) tr[p][u]=++tot; p=tr[p][u]; }}void dfs(int u,int f,int sum){ insert(sum),v.pb(sum); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==f) continue; dfs(j,u,sum^w[i]); }}int query(int x){ int p=0,ans=0; for(int i=30;i>=0;i--) { int u=x>>i&1; if(tr[p][!u]) { p=tr[p][!u]; ans+=(1<

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/107630984 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：POJ - 3723 Conscription 最小生成树

下一篇：hdu 3333 Turing Tree 线段树 + 离线

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章