P3292 [SCOI2016]幸运数字

2018-09-03 15:25:55


题意:询问树上两点间的最大异或和

最大异或和可以用线性基解决

先树剖,用线段树维护每一条链的最大异或和就搞定了

注意pushup的不同

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
typedef long long ll;
const int N=2e4+5;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,num,head[N],fa[N],son[N],tot[N];
int cnt,idx[N],dep[N],top[N];
ll w[N],a[N],s[N<<2][63],f[65],tmp[65];
inline ll read()
{
    ll x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=0;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return w?x:-x;
}
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k,int father,int deep)
{
    int bigson=0;
    fa[k]=father; dep[k]=deep; tot[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==father) continue;
        dfs(v,k,deep+1); tot[k]+=tot[v];
        if (bigson<tot[v])
        {
            bigson=tot[v]; son[k]=v;
        }
    }
}
void dfs(int k,int tp)
{
    idx[k]=++cnt; top[k]=tp; a[cnt]=w[k];
    if (!son[k]) return; dfs(son[k],tp);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!idx[v]) dfs(v,v);
    }
}
inline void insert(ll *a,ll x)
{
    for (reg int i=60;~i;i--)
      if (x&(1ll<<i))
        if (!a[i]) {a[i]=x; break;}
        else x^=a[i];
}
inline void merge(ll *a,ll *b)
{
    for (reg int i=60;~i;i--)
      if (b[i]) insert(a,b[i]);
}
inline ll query()
{
    ll ans=0;
    for (reg int i=60;~i;i--)
      if (ans<(ans^f[i])) ans^=f[i];
    return ans;
}
void build(int l,int r,int now)
{
    if (l==r)
    {
        insert(s[now],a[l]); return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1); build(mid+1,r,now<<1|1);
    merge(s[now],s[now<<1]); merge(s[now],s[now<<1|1]);
}
void Query(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return;
    if (l>=L&&r<=R) {merge(tmp,s[now]); return;}
    int mid=(l+r)>>1;
    if (mid>=R) Query(L,R,l,mid,now<<1);
    else if (mid<L) Query(L,R,mid+1,r,now<<1|1);
    else
    {
        Query(L,mid,l,mid,now<<1);
        Query(mid+1,R,mid+1,r,now<<1|1);
    }
}
inline ll getans(int x,int y)
{
    memset(f,0,sizeof(f));
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        memset(tmp,0,sizeof(tmp));
        Query(idx[top[x]],idx[x],1,n,1);
        merge(f,tmp); x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    memset(tmp,0,sizeof(tmp));
    Query(idx[x],idx[y],1,n,1);
    merge(f,tmp); return query();
}
int main()
{
    n=read(),m=read();
    for (reg int i=1;i<=n;w[i++]=read());
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add_edge(x,y); add_edge(y,x);
    }
    dfs(1,0,1); dfs(1,1); build(1,n,1);
    while (m--)
    {
        int x=read(),y=read();
        printf("%lld\n",getans(x,y));
    }
    return 0;
}