题意：一颗带点权的树，求树上两点间异或值最大子集的异或值

---

显然要用线性基

可以用倍增的思想，维护每个点向上\(2^j\)个祖先这些点的线性基，求lca的时候合并起来就行了

复杂度\(O(nlogn60*60)\)

注意这是点权，特判x==y的情况，需要插入a[x]

还可以用点分治和树链剖分

我的代码好慢啊...但是很好写啊

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;#define pii pair
         
          #define fir first#define sec secondconst int N=2e4+5;inline ll read() { char c=getchar(); ll x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int n, Q, u, v; ll a[N];struct edge{int v, ne;}e[N<<1];int cnt=1, h[N];inline void ins(int u, int v) { e[++cnt]=(edge){v, h[u]}; h[u]=cnt; e[++cnt]=(edge){u, h[v]}; h[v]=cnt;}namespace lb{ struct meow { ll p[62]; meow(){memset(p, 0, sizeof(p));} ll operator [](int x) {return p[x];} bool insert(ll val) { for(int i=60; i>=0; i--) if(val & (1LL<
          
           0; } void merge(meow &a) { for(int i=60; i>=0; i--) if(a[i]) insert(a[i]); } ll getmax() { ll ans=0; for(int i=60; i>=0; i--) ans = max(ans, ans^p[i]); return ans; } void print() { for(int i=60; i>=0; i--) if(p[i]) printf("p %d %lld\n",i,p[i]); puts(""); } }b[N][17];}using lb::b; using lb::meow;int fa[N][17], deep[N];void dfs(int u) { for(int i=1; (1<
           
            <=deep[u]; i++) { fa[u][i] = fa[ fa[u][i-1] ][i-1]; b[u][i].merge(b[u][i-1]); b[u][i].merge(b[ fa[u][i-1] ][i-1]); } for(int i=h[u];i;i=e[i].ne) if(e[i].v != fa[u][0]) { fa[e[i].v][0]=u; deep[e[i].v]=deep[u]+1; b[e[i].v][0].insert(a[u]); dfs(e[i].v); }}meow lca(int x, int y) { //printf("lca %d %d\n",x,y); meow now; if(x==y) {now.insert(a[x]); return now;} if(deep[x]
            
             =0; i--) if(fa[x][i] != fa[y][i]) now.merge(b[x][i]), now.merge(b[y][i]), x=fa[x][i], y=fa[y][i]; now.merge(b[x][0]); now.insert(a[y]); //puts("now");now.print(); return now;}ll Que(int x, int y) { return lca(x, y).getmax();}int main() { freopen("in","r",stdin); n=read(); Q=read(); for(int i=1; i<=n; i++) a[i]=read(), b[i][0].insert(a[i]); for(int i=1; i