[文章目录]
Description
给你一张n个点m条边的无向图，求一条1->n的路径，使得路径上的边权亦或和最大。n<=50000 m<=10^5 边权<=10^18
由于是无向图，通过同一条路径走到一个环上再走回来，路径的代价会抵消。那么答案相当于一条1到n的路径和一些环的亦或和。
对于无向图的边集，搜出一个树边集。枚举非树边，对于每个非树边连接到树上和树上的链形成的环记录亦或和，求线性基。答案等于树上1到n的亦或和在线性基中求得的最大值。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
int n,m;
int head[51000],to[201000],nxt[201000],cnt;
ll f[201000];
inline void add(int x,int y,ll z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
int fa[51000];
int find(int x){return fa[x]==x ? x:fa[x]=find(fa[x]);}
struct edge
{
int a,b;
ll w;
}a[101000];
ll dep[51000],lin[100];
void dfs(int x,int pre)
{
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
dep[to[i]]=dep[x]^f[i];
dfs(to[i],x);
}
}
void insert(ll x)
{
for(int i=62;i>=0;--i) if(x&(1ll<<i))//NOTE: 1+"ll" How foolish I am!
{
if(lin[i]) x^=lin[i];
else {lin[i]=x; break;}
}
}
int main()
{
scanf("%d%d",&n,&m);
int i; for(i=1;i<=n;++i) fa[i]=i;
i=1;
while(i<=m)
{
scanf("%d%d%llu",&a[i].a,&a[i].b,&a[i].w);
if(find(a[i].a)!=find(a[i].b))
{
add(a[i].a,a[i].b,a[i].w);
fa[find(a[i].a)]=find(a[i].b);
--m;
}
else ++i;
}
dfs(1,0);
for(i=1;i<=m;++i) insert(a[i].w^dep[a[i].a]^dep[a[i].b]);
ll ans=dep[n];
for(i=62;~i;--i) if((ans^lin[i])>ans) ans^=lin[i];
printf("%llu\n",ans);
return 0;
}