【bzoj1954】【The xor-longest Path】【trie树】-白红宇的个人博客

【bzoj1954】【The xor-longest Path】【trie树】

发布日期：2021-11-16 15:38:37 浏览次数：29 分类：技术文章

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

Description

给定一棵n个点的带权树，求树上最长的异或和路径

Input

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input

4
1 2 3
2 3 4
2 4 6

Sample Output

HINT

The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4)

注意：结点下标从1开始到N....

题解：两个点到根的异或和异或一下就是这两个点之间的异或和。

所以只要统计出所有点到根的异或和,放到trie树里面。

然后在trie树里面依次查询每个点的最大异或即可。

代码：

#include
    
     #include
     
      #include
      
       #define N 100010using namespace std;int point[N],next[N<<1],x,y,v,cnt,n,ans,a[N];struct use{int st,en,v;}e[N<<1];struct trie{  int ch[N*30][2],cnt;  void insert(int x){    int now(0);    for (int i=30;i>=0;i--){      int t=x&(1<
       
        >=i;      if (!ch[now][t]) ch[now][t]=++cnt;          now=ch[now][t];     }  }  int query(int x){    int now(0),temp(0);    for (int i=30;i>=0;i--){      int t=x&(1<
        
         >=i;      if (ch[now][t^1]) temp+=1<

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

上一篇：【bzoj3689】【异或之】【trie树+堆】

下一篇：【bzoj3620】【似乎在梦中见过的样子】【kmp】

发表评论

关于作者

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

-- 愿君每日到此一游！