题目概述

给出一棵树，求从 $x$ 到 $y$ ，经过的每个点都可以决定异或还是不异或，求能够得到的最大异或值。

解题报告

倍增+线性基就好啦，复杂度为 $O(60^2nlog_2n)$ ，这是假的完全过不了，但就是过了……正常点的解法好像是点分……我不会……

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=20000,Log=15,Len=60;

int n,te,dep[maxn+5],ST[maxn+5][Log+5];LL w[maxn+5],M[maxn+5][Log+5][Len+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline void Insert(LL *M,LL x) {for (int j=Len;~j;j--) if (x>>j&1) if (!M[j]) {M[j]=x;break;} else x^=M[j];}
inline void Merge(LL *x,LL *y) {for (int j=0;j<=Len;j++) if (y[j]) Insert(x,y[j]);}
void Dfs(int x,int pre=0){
    for (int j=(dep[x]=dep[pre]+1,ST[x][0]=pre,1);j<=Log;j++)
        Merge(M[x][j],M[x][j-1]),Merge(M[x][j],M[ST[x][j-1]][j-1]),ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);
}
inline LL Max(LL *x) {LL ans=0;for (int j=Len;~j;j--) if ((ans^x[j])>ans) ans^=x[j];return ans;}
inline LL Ask(int x,int y){
    static LL now[Len+5];for (int j=0;j<=Len;j++) now[j]=0;if (dep[x]<dep[y]) swap(x,y);
    for (int j=Log;dep[x]>dep[y]&&~j;j--) if (dep[ST[x][j]]>=dep[y]) Merge(now,M[x][j]),x=ST[x][j];
    if (x==y) return Insert(now,w[x]),Max(now);
    for (int j=Log;~j;j--) if (ST[x][j]!=ST[y][j]) Merge(now,M[x][j]),Merge(now,M[y][j]),x=ST[x][j],y=ST[y][j];
    return Insert(now,w[x]),Insert(now,w[y]),Insert(now,w[ST[x][0]]),Max(now);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&te);for (int i=1;i<=n;i++) scanf("%lld",&w[i]),Insert(M[i][0],w[i]);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);Dfs(1);
    for (int x,y;te;te--) scanf("%d%d",&x,&y),printf("%lld\n",Ask(x,y));return 0;
}