[Scoi 2016] 幸运数字

题目描述：

给出一棵树

树上有 N 个点 每个点有一个权值 C

给出 M 个 询问

问从 u->lca(u,v)->v 路径上任取任意数量的权值Xor最大是多少？

题目分析：

对于任取 数字 使其 Xor和最大的问题，是由线性基来解决的

我们可以把路径上的点值插入到一个线性基中，进行查询

暴力插入肯定是不行的 考虑倍增优化 每次我们只需要合并两个链的线性基即可

倍增预处理 O（NlogN）查询是 O（logN）

题目链接：

Luogu 3292

BZOJ 4568

Ac 代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
const int maxm=; 
int head[maxm],to[maxm<<],net[maxm<<],cnt;
ll f[maxm][][],ans[];
int fa[maxm][];
int deep[maxm],n,q;
inline void addedge(int u,int v)
{
    cnt++;
    to[cnt]=v,net[cnt]=head[u],head[u]=cnt;
}
inline void add(ll *a,ll x)
{
    for(int i=;~i;i--)
    if((x>>i)&)
    {
        if(!a[i]) 
        {
            a[i]=x;
            return;
        }
        x^=a[i];
    }
}
inline void merge(ll *a,ll *b){for(int i=;~i;i--) if(b[i]) add(a,b[i]);}
void dfs(int now,int fax,int dep)
{
    deep[now]=dep,fa[now][]=fax;
    for(int i=;i<=;i++)
    if(fa[now][i-])
    {
        fa[now][i]=fa[fa[now][i-]][i-];
        memcpy(f[now][i],f[now][i-],sizeof(f[now][i-]));
        merge(f[now][i],f[fa[now][i-]][i-]);
    }
    for(int i=head[now];i;i=net[i])
    if(to[i]!=fax)
     dfs(to[i],now,dep+);
}
inline int lca(int u,int v)
{
    memset(ans,,sizeof(ans));
    if(deep[u]<deep[v]) std::swap(u,v);
    int tmp=deep[u]-deep[v];
    for(int i=;~i;i--)
     if((tmp>>i)&) merge(ans,f[u][i]),u=fa[u][i];
    if(u==v) return u;
    for(int i=;~i;i--)
     if(fa[u][i]!=fa[v][i])
     {
        merge(ans,f[u][i]),merge(ans,f[v][i]);
        u=fa[u][i],v=fa[v][i];
     }
    merge(ans,f[u][]),merge(ans,f[v][]);  
    return fa[u][];
}
inline ll getans(int u,int v)
{
    int LCA=lca(u,v);
    merge(ans,f[LCA][]);
    ll res=;
    for(ll i=;~i;i--)
     res=std::max(res,res^ans[i]);
    return res;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        add(f[i][],x);
    }

    for(int i=;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v),addedge(v,u);
    }
    dfs(,,);
    for(int i=;i<=q;i++) 
    {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%lld\n",getans(u,v));
    }
    return ;
}