题解 P4551 【最长异或路径】
顾z
2018-08-03 06:30:11
**题目描述**
给定一棵 n 个点的带权树，结点下标从 1 开始到 N 。寻找树中找两个结点，求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
**个人**：
首先强推一下01字典树(Trie),这个东西是解决**xor问题**的利器.
查找最大异或值的时候我们一般从最高位到低位向下找
eg: 1000(2)=8(10)
0111(2)=7(10)
显然只要我的最高位是1,除非你和我的最高位相同,要不然我就是比你大.
根据数学上的等比数列求和可知
8=2^3 ，7=2^3-1
所以说我们可以**贪心的去找当前位^1的节点**
01字典树的写法和trie树差不多,对于这个题,
过程：
1.建图跑一下再去dfs去求每个节点到根节点的xor值。
2.再去构建01Trie去实现我们的贪心即可
~~网上讲这个的很多,想学的可以百度~~
———————代码—————————
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define maxn 100008
int trie[maxn*31][2],xo[maxn],ans,rt;
int val[maxn],n,head[maxn],tot;
struct code{int u,v,w;}edge[maxn<<1];
IL void read(int &x){
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x*=f;
}
IL void add(int x,int y,int z)
{
edge[++tot].u=head[x];
edge[tot].v=y;
edge[tot].w=z;
head[x]=tot;
edge[++tot].u=head[y];
edge[tot].v=x;
edge[tot].w=z;
head[y]=tot;
}
IL void build_trie(int x,int rt)
{
for(RI i=1<<30;i;i>>=1)
{
bool c=x&i;
if(!trie[rt][c])trie[rt][c]=++tot;
rt=trie[rt][c];
}
}
IL int query(int x,int rt)
{
int ans=0;
for(RI i=1<<30;i;i>>=1)
{
bool c=x&i;
if(trie[rt][c^1])ans+=i,rt=trie[rt][c^1];
else rt=trie[rt][c];
}
return ans;
}
IL void dfs(int u,int fa)
{
for(RI i=head[u];i;i=edge[i].u)
{
if(edge[i].v!=fa)
{
xo[edge[i].v]=xo[u]^edge[i].w;
dfs(edge[i].v,u);
}
}
}
int main()
{
read(n);
for(RI i=1,u,v,w;i<n;i++)read(u),read(v),read(w),add(u,v,w);
dfs(1,0);
for(RI i=1;i<=n;i++)build_trie(xo[i],rt);
for(RI i=1;i<=n;i++)ans=std::max(ans,query(xo[i],rt));
printf("%d",ans);
}
```