点分，处理每个点到根的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);
    }
}