4e4+1000(wa8) 4e5(AC)

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=4e5+100;
typedef int LL;
struct Query{
    LL l,r,ll,rr,lca;
    LL id;
}q[100010];
bool vis[maxn];
LL a[maxn],b[maxn];
LL cnt[maxn];
LL answer[maxn];
LL sum=0;
///莫队部分
bool cmp(Query A,Query B){
    if(A.ll!=B.ll){
        return A.ll<B.ll;
    }
    if(A.ll&1) return A.rr>B.rr;
    else return A.rr<B.rr;
}
void add(LL x){
    cnt[a[x]]++;
    if(cnt[a[x]]==1) sum++;
}
void del(LL x){
    cnt[a[x]]--;
    if(cnt[a[x]]==0) sum--;
}
void cal(LL x){
    ///每个节点都有一个颜色
    (!vis[x])?add(x):del(x);
    vis[x]^=1;
}
///树链剖分部分(求LCA)
LL times=0;
LL siz[maxn],top[maxn],dep[maxn],fa[maxn],son[maxn];
vector<LL>g[maxn];
LL numid[maxn*2],st[maxn],ed[maxn];
void predfs(LL u,LL father){
    siz[u]=1;dep[u]=dep[father]+1;
    fa[u]=father;
    st[u]=++times;
    numid[times]=u;
    for(LL i=0;i<g[u].size();i++){
        LL v=g[u][i];
        if(v==father) continue;
        predfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]){
            son[u]=v;
        }
    }
    ed[u]=++times;numid[times]=u;///欧拉序
}
void dfs(LL u,LL topx){
     top[u]=topx;
     if(!son[u]) return;
     dfs(son[u],topx);
     for(LL i=0;i<g[u].size();i++){
        LL v=g[u][i];
        if(v==fa[u]||v==son[u]) continue;
        dfs(v,v);
     }
}
LL getLCA(LL u,LL v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return u;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n,m;cin>>n>>m;
  for(LL i=1;i<=n;i++){
    cin>>a[i];b[i]=a[i];
  }
  sort(b+1,b+1+n);
  LL siz=unique(b+1,b+1+n)-b-1;
  for(LL i=1;i<=n;i++){
    a[i]=lower_bound(b+1,b+1+siz,a[i])-b;///离散化
  }
  for(LL i=1;i<n;i++){
    LL u,v;cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  predfs(1,0);
  dfs(1,1);
  LL block=sqrt(n*2);
  for(LL i=1;i<=m;i++){
    LL u,v;cin>>u>>v;
    if(st[u]>st[v]) swap(u,v);///先被访问的放前面
    LL LCA=getLCA(u,v);
    ///u和v在同一个子树内
    if(LCA==u||LCA==v){
        q[i].id=i;
        q[i].l=st[u];q[i].r=st[v];
        q[i].ll=(st[u]-1)/block+1;///l端点分到的块的编号
        q[i].rr=(st[v]-1)/block+1;///r端点分到的块的编号
        q[i].lca=0;
    }
    ///u和v不在同一棵子树内
    else{
        q[i].id=i;
        q[i].l=ed[u];q[i].r=st[v];
        q[i].ll=(ed[u]-1)/block+1;q[i].rr=(st[v]-1)/block+1;
        q[i].lca=LCA;///最后要加上LCA的贡献
    }
  }
  LL L=1;LL R=0;
  sort(q+1,q+1+m,cmp);
  for(LL i=1;i<=m;i++){
     while(L<q[i].l) cal(numid[L++]);///该树的节点
     while(L>q[i].l) cal(numid[--L]);
     while(R<q[i].r) cal(numid[++R]);
     while(R>q[i].r) cal(numid[R--]);
     if(q[i].lca){
        cal(q[i].lca);
     }
     answer[q[i].id]=sum;
     if(q[i].lca){
        cal(q[i].lca);
     }
  }
  for(LL i=1;i<=m;i++){
    cout<<answer[i]<<endl;
  }
return 0;
}