bzoj4568(合并线性基+倍增)

裸题练习模板

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int maxn=;

vector<ll>v[maxn][];

int d[maxn],n,Q,fa[maxn][],last[maxn],pre[maxn],other[maxn],t;

void add(int x,int y){++t;pre[t]=last[x];last[x]=t;other[t]=y;}

ll x,q[maxn];

vector<ll> uni(vector<ll> a,vector<ll> b){

    vector<ll>ans;

    int top=,lena=a.size(),lenb=b.size();

    for(int i=;i<lena;++i)q[++top]=a[i];

    for(int i=;i<lenb;++i)q[++top]=b[i];

    int p=;

    for(int j=;j>=;--j){

        bool flag=;

        for(int i=p+;i<=top;++i)

        if((q[i]>>j)&){

            swap(q[i],q[++p]);

            flag=;break;

        }

        if(!flag)continue;

        for(int i=;i<=top;++i)

        if(i!=p){

            if((q[i]>>j)&)q[i]^=q[p];

        }

    }

    for(int i=;i<=p;++i)ans.push_back(q[i]);

    return ans;

}

void dfs(int x){

    for(int i=last[x];i;i=pre[i]){

        int v=other[i];

        if(v==fa[x][])continue;

        d[v]=d[x]+;fa[v][]=x;

        dfs(v);

    }

}

int lca(int x,int y){

    if(d[x]<d[y])swap(x,y);

    for(int i=;i>=;--i)

    if(d[fa[x][i]]>=d[y])x=fa[x][i];

    if(x==y)return x;

    for(int i=;i>=;--i)

    if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    return fa[x][];

}

int jump(int x,int y){

    for(int i=;i>=;--i){

        if((<<i)&y)x=fa[x][i];

    }

    return x;

}

vector<ll> qs(int x,int y){

    int k=log2(d[x]-d[y]+);

    return uni(v[x][k],v[jump(x,d[x]-d[y]+-(<<k))][k]);

}

int main(){

    cin>>n>>Q;

    for(int i=;i<=n;++i){

        scanf("%lld",&x);

        v[i][].push_back(x);

    }

    int a,b,tmp;

    for(int i=;i<n;++i){

        scanf("%d%d",&a,&b);

        add(a,b);add(b,a);

    }

    dfs();

    for(int j=;j<=;++j)

    for(int i=;i<=n;++i){

        fa[i][j]=fa[fa[i][j-]][j-];

        v[i][j]=uni(v[i][j-],v[fa[i][j-]][j-]);

    }

    while(Q--){

        scanf("%d%d",&a,&b);

        tmp=lca(a,b);

        vector<ll>ans=uni(qs(a,tmp),qs(b,tmp));

        ll res=,siz=ans.size();

        for(int i=;i<siz;++i)

        if((res^ans[i])>res)res^=ans[i];

        printf("%lld\n",res);

    }

    return ;

}