「SCOI2016」幸运数字

思路:

  线性基;

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 20005
#define ll long long
struct DataType {
ll d[],p[];
ll cnt;
DataType()
{
memset(d,,sizeof(d));
memset(p,,sizeof(p));
cnt=;
}
bool insert(long long val)
{
for(ll i=;i>=;i--)
{
if(val&(1LL<<i))
{
if(!d[i])
{
d[i]=val;
break;
}
val^=d[i];
}
}
return val>;
}
ll Max()
{
ll res=;
for(ll i=;i>=;i--)
{
if((res^d[i])>res) res^=d[i];
}
return res;
}
};
struct DataType ans;
struct TreeNodeType {
ll l,r,mid;
DataType data;
};
struct TreeNodeType tree[maxn<<];
ll n,m,deep[maxn],id[maxn],size[maxn],f[maxn],head[maxn];
ll E[maxn<<],V[maxn<<],tot,ai[maxn],bi[maxn],lar[maxn];
ll top[maxn];
inline void in(ll &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void edge_add(ll u,ll v)
{
E[++tot]=head[u],V[tot]=v,head[u]=tot;
E[++tot]=head[v],V[tot]=u,head[v]=tot;
}
void merge(DataType &a,DataType b)
{
for(ll i=;i<=;i++)
{
if(b.d[i]) a.insert(b.d[i]);
}
}
void dfs1(ll now,ll fa)
{
f[now]=fa,deep[now]=deep[fa]+,size[now]=;
for(ll i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
dfs1(V[i],now),size[now]+=size[V[i]];
if(size[lar[now]]<size[V[i]]) lar[now]=V[i];
}
}
void dfs2(ll now,ll chain)
{
top[now]=chain,id[now]=++tot,bi[tot]=ai[now];
if(lar[now])
{
dfs2(lar[now],chain);
for(ll i=head[now];i;i=E[i])
{
if(V[i]==lar[now]||V[i]==f[now]) continue;
dfs2(V[i],V[i]);
}
}
}
void build(ll now,ll l,ll r)
{
tree[now].l=l,tree[now].r=r;
if(l==r)
{
tree[now].data.insert(bi[l]);
return;
}
tree[now].mid=l+r>>;
build(now<<,l,tree[now].mid),build(now<<|,tree[now].mid+,r);
tree[now].data=tree[now<<].data;
merge(tree[now].data,tree[now<<|].data);
}
void query(ll now,ll l,ll r)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
merge(ans,tree[now].data);
return;
}
if(l<=tree[now].mid) query(now<<,l,r);
if(r>tree[now].mid) query(now<<|,l,r);
}
ll query(ll x,ll y)
{
for(int i=;i<=;i++) ans.d[i]=,ans.p[i]=;
ans.cnt=;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) query(,id[top[y]],id[y]),y=f[top[y]];
else query(,id[top[x]],id[x]),x=f[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
query(,id[x],id[y]);
return ans.Max();
}
int main()
{
freopen("data.txt","r",stdin);
in(n),in(m);ll u,v;
for(ll i=;i<=n;i++) in(ai[i]);
for(ll i=;i<n;i++)in(u),in(v),edge_add(u,v);
dfs1(,),tot=,dfs2(,),build(,,n);
while(m--) in(u),in(v),printf("%lld\n",query(u,v));
return ;
}
05-11 01:53