[评测记录](https://vjudge.csgrandeur.cn/solution/43631441)
by Augury @ 2023-06-16 15:56:32
@[Augury](/user/401461)
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;bool op=0;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')op=1;ch=getchar();}
while('0'<=ch&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
if(op)return -ans;
return ans;
}
const int maxn=1e5+10;
int n,m;
int Block;
struct query{
int u,v;
int l,r;
int lca,id;
bool operator < (const query cmp)const{
if(l/Block==cmp.l/Block)return r<cmp.r;
return l/Block<cmp.l/Block;
}
}q[maxn];
int a[maxn];
vector<int>g[maxn];
int euler[maxn],node=0;
pair<int,int>mp[maxn];
int fa[20][maxn],dep[maxn];
int buc[maxn],res,vis[maxn];
int ans[maxn];
void init(){
vector<int>mp;
for(int i=1;i<=n;i++)mp.push_back(a[i]);
sort(mp.begin(),mp.end());
mp.erase(unique(mp.begin(),mp.end()),mp.end());
for(int i=1;i<=n;i++)a[i]=lower_bound(mp.begin(),mp.end(),a[i])-mp.begin();
}
void dfs(int now){
euler[++node]=now;
mp[now].first=node;
for(int i=1;i<=19;i++)fa[i][now]=fa[i-1][fa[i-1][now]];
dep[now]=dep[fa[0][now]]+1;
for(int nxt:g[now]){
if(nxt==fa[0][now])continue;
fa[0][nxt]=now;
dfs(nxt);
}
euler[++node]=now;
mp[now].second=node;
}
int lca(int a,int b){
if(dep[a]<dep[b])swap(a,b);
for(int i=19;~i;--i){
if(dep[fa[i][a]]<dep[b])continue;
a=fa[i][a];
}
if(a==b)return a;
for(int i=19;~i;--i){
if(fa[i][a]==fa[i][b])continue;
a=fa[i][a],b=fa[i][b];
}
return fa[0][a];
}
void ins(int pos){
if(!buc[pos])++res;
++buc[pos];
}
void era(int pos){
--buc[pos];
if(!buc[pos])--res;
}
void work(int pos){
if(vis[pos]) era(a[pos]); else ins(a[pos]);
vis[pos]^=1;
}
void sol(){
int l=1,r=0;
for(int i=1;i<=m;i++){
while(r<q[i].r)work(euler[++r]);
while(l>q[i].l)work(euler[--l]);
while(r>q[i].r)work(euler[r--]);
while(l<q[i].l)work(euler[l++]);
if(~q[i].lca)work(q[i].lca);
ans[q[i].id]=res;
if(~q[i].lca)work(q[i].lca);
}
}
signed main(){
n=read(),m=read();
Block=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read();
init();
for(int i=1;i<n;i++){
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for(int i=1;i<=m;i++){
int u=read(),v=read();
if(mp[u].first>mp[v].first)swap(u,v);
if(mp[v].second<mp[u].second){
q[i]=(query){u,v,mp[u].first,mp[v].first,-1,i};
}
else{
q[i]=(query){u,v,mp[u].second,mp[v].first,lca(u,v),i};
}
}
sort(q+1,q+1+m);
sol();
for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
return 0;
}
```
by LgxTpre @ 2023-06-16 16:26:37
@[LgxTpre](/user/66709) ？
by Augury @ 2023-06-16 16:30:53