点分，处理每个点到根的bitset，询问时或一下两个bitset。
但是由于可持久化树存储的bitset或运算会很慢，在q*n/32本来就是时间瓶颈的情况下显然是不好的，
所以我想不用可持久化bitset，而是直接每个点都新开个bitset。
注意到实际上bitset只用当前分治处理的这棵树的信息，所以离散化一下，大小就变成O(树的大小)了
于是复杂度就是O(n^2/32+n^2/2/32+..n^2/n/32)=O(n^2/32)。
于是我没有把int全部替换成unsigned short，也没有在分治的树小的时候暴力等等，就拿到了bzoj rank1。
#include<bits/stdc++.h>
using std::sort;
#define us unsigned short
#define ui unsigned int
const int N=40010;
struct edge
{
int to,next;
}l[N<<1];int e;
int a[N],t[N];
int n,i,x,y;
bool xiao(int *x,int *y)
{
return *x<*y;
}
void lisan()
{
static int *q[N],top;
for(i=1;i<=n;++i)q[i]=a+i;
sort(q+1,q+n+1,xiao);
int now=-1;
for(i=1;i<=n;++i)
{
if(*q[i]!=now){now=*q[i];++top;}
*q[i]=top;
}
}
us t_f[N],deep[N];
ui *b[17][N],**now_b,*X,*Y;
us U[N];
bool vis[N];
us q[N],head,tail,sz[N];
us cnt[N],mx;
us f[N];
void build(us rt,us dep,us fr)
{
for(;mx;--mx)cnt[mx]=0;
f[q[tail=1]=rt]=0;
for(head=1;head<=tail;++head)
{
x=q[head];sz[x]=1;
cnt[a[x]]=1;if(a[x]>mx)mx=a[x];
for(i=t[x];y=l[i].to;i=l[i].next)
if(!vis[y]&&y!=f[x])
f[q[++tail]=y]=x;
}
for(i=2;i<=mx;++i)cnt[i]+=cnt[i-1];
while(x=q[--head])
{
if((sz[x]<<1)>=tail)break;
sz[f[x]]+=sz[x];
}
rt=x;
t_f[rt]=fr;deep[rt]=dep;
vis[rt]=1;
now_b=b[dep];
f[q[tail=1]=rt]=0;
us u=(cnt[mx]>>5)+1; U[rt]=u;
for(head=1;head<=tail;++head)
{
x=q[head];a[x]=cnt[a[x]];
now_b[x]=new ui [u];
if(head>1) for(i=0;i<u;++i)now_b[x][i]=now_b[f[x]][i];
else for(i=0;i<u;++i)now_b[x][i]=0;
now_b[x][a[x]>>5]|=1<<(a[x]&31);
for(i=t[x];y=l[i].to;i=l[i].next)
if(!vis[y]&&y!=f[x])
{
f[y]=x;q[++tail]=y;
}
}
++dep;
for(int i=t[rt];y=l[i].to;i=l[i].next)
if(!vis[y]) build(y,dep,rt);
}
us get_lca(us x,us y)
{
while(x!=y)
if(deep[x]>deep[y])x=t_f[x];
else y=t_f[y];
return x;
}
namespace kcz
{
const int U=1<<16;
us f[U+1];
void init()
{
for(i=1;i<=U;++i)f[i]=f[i-(i&-i)]+1;
}
us count(ui x)
{
return f[x&(U-1)]+f[x>>16];
}
};
const int ch_top=5000000;
char ch[ch_top],*now_r=ch;
void read(int &x)
{
while(*now_r<'-')++now_r;
if(*now_r=='-')
{
for(x=*++now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
x=-x;
}
else
{
for(x=*now_r-'0';*++now_r>='0';) x=(x<<1)+(x<<3)+*now_r-'0';
}
}
us ans;
int main()
{
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
int q;
fread(ch,1,ch_top,stdin);
read(n);read(q);
for(i=1;i<=n;++i)read(a[i]);
lisan();
for(i=1;i<n;++i)
{
read(x);read(y);
l[++e]=(edge){y,t[x]};t[x]=e;
l[++e]=(edge){x,t[y]};t[y]=e;
}
build(1,0,0);
kcz::init();
while(q--)
{
read(x);read(y);//x=x^ans;
us lca=get_lca(x,y);
X=b[deep[lca]][x];Y=b[deep[lca]][y];
ans=0;
for(i=0;i<U[lca];++i) ans+=kcz::count(X[i]|Y[i]);
printf("%d\n",ans);
}
}
鄂公网安备 42010202000505 号