【P4551 最长异或路径】题解
题目链接
题目
给定一棵 \(n\) 个点的带权树,结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点,求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或
思路
预处理每个点到根节点路劲的异或和,建一棵01trie树。
对于每个节点,在trie树上找离它最远的节点,最后取个 \(\max\) 值即可。
总结
这道题应该也算两个经典问题的集合吧?
首先求树上两个节点之间路径的异或和,这是一个非常经典的问题,由于重复异或没影响,所以可以用树形dp预处理。
这道题巧妙就巧妙在他运用了Trie树,出现异或,还要求最大,trie树是一种非常常用的方法,遇到这种情况可以往Trie树的方面来想。
Code
// Problem: P4551 最长异或路径
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4551
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 100010
struct node
{
int x, y, z, n;
}dx[N*2];
struct Node
{
int s[2];
}d[N*30];
int n, m, i, j, k;
int dp[N], u, v, w, h[N];
int ans, cnt;
void cun(int x, int y, int z)
{
dx[++k].x=x; dx[k].y=y; dx[k].z=z;
dx[k].n=h[x]; h[x]=k;
}
void dfs(int x, int fa)
{
for(int g=h[x]; g; g=dx[g].n)
{
int y=dx[g].y;
if(y==fa) continue;
dp[y]=dp[x]^dx[g].z;
dfs(y, x);
}
}
void trie(int x)
{
int i, j, p=1;
for(i=30; i>=0; --i)
{
j=(x&(1<0;
if(!d[p].s[j]) d[p].s[j]=++cnt;
p=d[p].s[j];
}
}
int find(int dep, int x, int p)
{
if(dep<0) return 0;
int i=(x&(1<0;
return find(dep-1, x, (d[p].s[i^1] ? d[p].s[i^1] : d[p].s[i]) )+(d[p].s[i^1] ? (1<