题目描述

给定一棵n个点的带权树，结点下标从1开始到N。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入输出格式

输入格式：

第一行一个整数N，表示点数。

接下来 n−1行，给出 u,v,w ，分别表示树上的 u 点和 v 点有连边，边的权值是 w。

输出格式：

一行，一个整数表示答案。

输入输出样例

输入样例#1：

4 1 2 3 2 3 4 2 4 6

输出样例#1：

7

说明

最长异或序列是1-2-3，答案是 7 (=3 ⊕ 4)

---

\(Solution\)

嗯，一道Trie树板子题……

题解背景：曾经有一次模拟赛考过这个题目，但我没有落实，等到再考一次的时候才后悔莫及。

总思路：首先可以 出每个节点到根节点的异或距离，然后把每个距离值丢到Trie树里，最后枚举一下就好了。

具体操作：

计算异或距离不讲，这里不需要考虑最近公共祖先的问题，因为公共祖先的那一段算了两次，异或和为零，没有任何影响。这里重点讲一下后面的操作。

x & ( 1 < < i ) 可以求出数 x 的二进制表示中第 i 位是多少，因为与运算全一为一，有零为零。另外建树时要注意使所有 x 的二进制位数相同。

void build(int v){    int x=0;    for(int i=31;i>=0;i--)    {        int a=(v&(1<
    
     >i;        if(!ch[x][a]) ch[x][a]=++cnt;//cnt表示这是第几号节点        x=ch[x][a];    }}
    

查询时由于你需要异或和最大，所以贪心一下就好了qwq

int query(int v){    int x=0,res=0;    for(int i=31;i>=0;i--)    {        int a=(v&(1<
    
     >i;        if(ch[x][!a]) res+=(1<
    

附上总代码：

#include
    
     #define il inlineusing namespace std;const int N=100010;il int read(){    int f=1,w=0;char c=0;    while(!isdigit(c))    {        if(c=='-') f=-1;        c=getchar();    }    while(isdigit(c)) w=w*10+(c^48),c=getchar();    return f*w;}int n,dis[N],ch[10*N][2],tot,ans,cnt;int head[N],ver[2*N],edge[2*N],nex[2*N];void add(int x,int y,int z){    ver[++tot]=y,edge[tot]=z,nex[tot]=head[x],head[x]=tot;}void dfs(int p,int f){    for(int i=head[p];i;i=nex[i])    {        int y=ver[i],z=edge[i];        if(y==f) continue;        dis[y]=(dis[p]^z);        dfs(y,p);    }}void build(int v){    int x=0;    for(int i=31;i>=0;i--)    {        int a=(v&(1<
     
      >i;        if(!ch[x][a]) ch[x][a]=++cnt;        x=ch[x][a];    }}int query(int v){    int x=0,res=0;    for(int i=31;i>=0;i--)    {        int a=(v&(1<
      
       >i;        if(ch[x][!a]) res+=(1<