利用线性基的合并，（直接暴力合并，复杂度62^2），当树上路径和来做。。。（然后跑的巨慢，但是可以优化哈哈）
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+7;
struct ShanHenKi { // 胡乱拼的
long long base[64];
inline bool insert(long long vec) {
for(int i=62; ~i; --i) {
if(!(vec>>i)) continue;
if(!base[i]) {base[i]=vec; return 1;}
vec^=base[i];
}
return 0;
}
inline ShanHenKi add(const ShanHenKi& d) {
ShanHenKi res=*this;
for(int i=62; ~i; --i) {
if(d.base[i]) res.insert(d.base[i]);
}
return res;
}
inline long long max() {
long long res=0;
for(int i=62; ~i; --i) {
if((res^base[i])>res) res^=base[i];
}
return res;
}
} dis[N][20];
int n,m;
int fa[N][20],dep[N];
vector<int> e[N];
void pre(int x,int pa) {
dep[x]=dep[fa[x][0]=pa]+1;
for(int i=1; (1<<i)<=dep[x]; ++i) {
fa[x][i]=fa[fa[x][i-1]][i-1];
dis[x][i]=dis[x][i-1].add(dis[fa[x][i-1]][i-1]);
}
for(int y:e[x]) if(y!=pa) {
pre(y,x);
}
}
long long query(int x,int y) {
ShanHenKi res;
memset(&res,0,sizeof res);
if(dep[x]<dep[y]) swap(x,y);
int dif=dep[x]-dep[y];
for(int i=19; ~i; --i) {
if(dif&(1<<i)) {
res=res.add(dis[x][i]), x=fa[x][i];
}
}
if(x==y) return res.add(dis[x][0]).max();
for(int i=19; ~i; --i) {
if(fa[x][i]!=fa[y][i]) {
res=res.add(dis[x][i]), x=fa[x][i];
res=res.add(dis[y][i]), y=fa[y][i];
}
}
res=res.add(dis[x][0]).add(dis[y][1]);
return res.max();
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; ++i) {
long long x;
scanf("%lld",&x);
dis[i][0].insert(x);
}
for(int i=n,x,y; --i; ) {
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
pre(1,0);
for(int i=m,x,y; i--; ) {
scanf("%d%d",&x,&y);
printf("%lldn",query(x,y));
}
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
