莫队入门题单

本文主要是介绍莫队入门题单，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考博客传送门①
参考博客传送门②
题单的传送门
(注意巧妙使用玄学卡常技巧,然后指针必须能够O(1)移动)

文章目录

普通莫队
- - [SPOJ - DQUERY](https://vjudge.net/problem/SPOJ-DQUERY)
  - [P2709 小B的询问](https://www.luogu.com.cn/problem/P2709)
  - [P1494 [国家集训队]小Z的袜子](https://www.luogu.com.cn/problem/P1494)
  - [CF617E XOR and Favorite Number](https://www.luogu.com.cn/problem/CF617E)
  - [P3709 大爷的字符串题](https://www.luogu.com.cn/problem/P3709)
带修改的莫队
- - [P1903 [国家集训队]数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
  - [F. Machine Learning](https://codeforces.com/contest/940/problem/F)
树上莫队
- - [ SPOJ - COT2 ](https://vjudge.net/problem/SPOJ-COT2)

普通莫队

SPOJ - DQUERY

题意：给定正整数序列，m次询问，每次询问区间不同数的个数。
（莫队板题）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int maxn = 1e6+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//每次求 [l,r] 不同的数的个数
int n,m,a[maxn];
int block;
int color[maxn];
int ans;
int ANS[maxn];
struct node 
{int l,r,id;
}q[maxn];
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void del(int x) 
{color[a[x]]--;if(color[a[x]] == 0) ans--;
}
inline void add(int x) 
{color[a[x]]++;if(color[a[x]] == 1) ans++;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i);scanf("%d",&m);for(int i=1;i<=m;i++) {scanf("%d %d",&q[i].l,&q[i].r);q[i].id=i;}block=n/sqrt(m*2/3);sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(int i=1;i<=m;i++) {int ql=q[i].l,qr=q[i].r;while(l<ql) del(l++);while(r>qr) del(r--);while(l>ql) add(--l);while(r<qr) add(++r);ANS[q[i].id]=ans;}for(int i=1; i<=m ;i++) {printf("%d\n",ANS[i]); }return 0;
}

P2709 小B的询问

题意：给定整数序列，每次询问一个区间内的 $\sum_{l}^{r} (c[i])^2$ ,c[i]表示数字i在[l,r]中出现的次数
(莫队板题，维护区间内数的个数，个数的平方数变化产生的贡献)

add : n² ->(n+1)² ，答案增加2n+1
del : n² ->(n-1)² ，答案增加-2n+1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 5e4+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定序列 求[l,r] 中 Σci² ci表示i出现的次数
int n,m,k;
int num[maxn];
int a[maxn];
ll ans=0;
ll ANS[maxn];
struct node 
{int l,r,id;
}q[maxn];
int block;
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void del(int x) 
{ans += (-2*num[a[x]]+1) ;num[a[x]]--;
}
inline void add(int x)
{ans += (2*num[a[x]]+1) ;num[a[x]]++;
}int main()
{scanf("%d %d %d",&n,&m,&k);block=n/sqrt(m*2/3);for(re int i=1;i<=n;i++) {scanf("%d",a+i);}for(re int i=1;i<=m;i++){scanf("%d %d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(re int i=1;i<=m;i++) {int ql=q[i].l,qr=q[i].r;while(l < ql) del(l++);while(r > qr) del(r--);while(l > ql) add(--l);while(r < qr) add(++r);ANS[q[i].id]=ans;}for(int i=1;i<=m;i++) printf("%lld\n",ANS[i]);return 0;
}

P1494 [国家集训队]小Z的袜子

题意：给定整数序列，m次询问,每次询问在区间[l,r]中随机取两个数时取中两个相同的数的概率。(最简分数表示)

用cnt[x]表示数x在区间内出现的次数，len表示当前区间长度，那么概率就为:
$\frac{\sum C_{2}^{cnt[x]} }{C_{2}^{len} }$

化简： $\frac{\sum (cnt[x]^2 -cnt[x]) }{len*(len-1)}$
进一步化简 : $\frac{\sum cnt[x]^2 -len }{len*(len-1)}$

于是每次指针移动，需要维护的信息就是一个平方数的贡献了。和第二题一样的维护方法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define re register
#pragma GCC optimize(2)
const int maxn = 6e4+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定序列 求在[l,r]中任选2个数时 抽中两个相同的数的概率 (用最简分数表示
//我们假设已经在一段区间求好了答案 用计数公式手推一下可以知道
//指针左右移动 需要维护的只是num[x]的平方项 
//加1  平方项增加2n+1  减1 平方项增加-2n+1
int n,m,block;
int a[maxn];
int num[maxn];
ll tot=0;//
ll ANS[maxn][2];
struct node 
{int l,r,id;
}q[maxn];
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void del(int x) 
{tot+=-2*num[a[x]]+1;num[a[x]]--;//这个数减少1个
}
inline void add(int x)
{tot+=2*num[a[x]]+1;num[a[x]]++;//这个数增加一个
}
int main()
{scanf("%d %d",&n,&m);block=n/sqrt(m*2/3);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=m;i++){scanf("%d %d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(int i=1;i<=m;i++) {int ql=q[i].l,qr=q[i].r;while(l<ql) del(l++);while(r>qr) del(r--);while(l>ql) add(--l);while(r<qr) add(++r);int L=r-l+1;if(L == 1) //特判的情况{ANS[q[i].id][0] = 0;ANS[q[i].id][1] = 1;continue;}ANS[q[i].id][0] = tot-L;//分子ANS[q[i].id][1] = 1ll*L*(L-1);//分母,坑:可能爆intll gd=__gcd(ANS[q[i].id][0],ANS[q[i].id][1]);ANS[q[i].id][0] /= gd;ANS[q[i].id][1] /= gd;}for(int i=1;i<=m;i++) {printf("%lld/%lld\n",ANS[i][0],ANS[i][1]);}return 0;
}

CF617E XOR and Favorite Number

题意：给定整数区间以及自然数k，m次询问，每次询问区间[l,r]有多少个子段满足异或结果为k 。

子段是连续的，我们可以想到用前缀异或数组来把子段异或运算简化成前缀数组的两个元素的异或。即：

$\oplus a[5] \oplus a[6] = (a[1] \oplus a[2]...a[6]) \oplus (a[1] \oplus a[2]\oplus a[3])$

问题就转化成:每次询问前缀异或数组中，[l-1,r]内有多少对(i,j)满足pre[i]^pre[j]==k

cnt[i]表示元素i出现的次数，指针移动的时候就可以O（1）维护答案了.

坑点，k可以等于0，此时删除的时候需要删的是cnt[i]-1个，而不是cnt[i]个

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 1e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定整数序列 给定常数k m次询问 每次问[l,r]中有多少个子段满足 异或结果为k
//子段 联想到预处理出前缀异或数组pre  a[i]^a[i+1]..^a[j] == pre[i-1]^pre[j]
//问题就成了求[l-1,r]中有多少个对 异或结果为k
int a[maxn],n,m,k,block;
struct node 
{int l,r,id;
}q[maxn];
ll num[20*maxn];//注意开到2e6  不然会re
ll ans[maxn],ret=0;
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block) ^ (b.l/block) ? a.l<b.l : (((a.l/block)&1) ? a.r < b.r:a.r>b.r) ;
}
inline void del(int x)
{ret-=num[a[x]^k];num[a[x]]--;if(!k) //k==0 此时a[x]^a[x]==k 应该删去num[a[x]]-1个 {ret++;}
}
inline void add(int x)
{ret+=num[a[x]^k];num[a[x]]++;
}
int main()
{scanf("%d %d %d",&n,&m,&k);block=sqrt(n);for(int i=1;i<=n;i++){int t;scanf("%d",&t);a[i]=a[i-1]^t;}for(int i=1;i<=m;i++) {scanf("%d %d",&q[i].l,&q[i].r);q[i].l--;//对应的pre数组区间是[l-1,r]q[i].id=i;}sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(int i=1;i<=m;i++){int ql=q[i].l,qr=q[i].r;while(l < ql) del(l++);while(l > ql) add(--l);while(r < qr) add(++r);while(r > qr) del(r--);ans[q[i].id]=ret;}for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);return 0;
}

P3709 大爷的字符串题

题目大意：给定正整数序列，m次询问，每次询问区间内众数的出现次数。

我们用num[i]表示数字i出现的次数，cnt[i]表示出现i次的数的个数, ans维护当前区间众数的出现次数
指针移动的时候，分别维护num[] ,cnt[] ,ans 就好了

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 2e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定整数序列 给定常数k m次询问 每次求区间 众数的出现次数
//num[i]表示元素i出现的次数 , cnt[i]表示 出现i次的数  一共有多少个 , ans记录当前区间众数的出现的次数
//add:cnt[num[i]]-- ,cnt[++num[i]]++  更新ans=max(ans,num[i]) 
//del:cnt[num[i]]-- ,cnt[--num[i]]++  如果删掉前a[i]是众数 且是唯一的一个众数 那么ans--
int n0,m,block;
int a[maxn],b[maxn],n;//离散化
int num[maxn],cnt[maxn];//i出现的次数  出现i次的数有多少个
int ans=0,ANS[maxn];//众数的出现次数
struct node 
{int l,r,id;
}q[maxn];
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block) ^ (b.l/block) ? a.l<b.l : (((a.l/block)&1) ? a.r < b.r:a.r>b.r) ;
}
inline void del(int x) 
{cnt[num[a[x]]]--;if(num[a[x]]==ans && !cnt[num[a[x]]]) ans--;//只有一个众数a[x],出现次数减了1cnt[--num[a[x]]]++;
}
inline void add(int x)
{cnt[num[a[x]]]--;cnt[++num[a[x]]]++;ans=max(ans,num[a[x]]);
}
int main()
{scanf("%d %d",&n0,&m);block=sqrt(n0);for(re int i=1;i<=n0;i++) {scanf("%d",a+i);b[i]=a[i];}sort(b+1,b+n0+1);n=unique(b+1,b+n0+1)-b-1;for(int i=1;i<=n0;i++) {a[i]=lower_bound(b+1,b+n+1,a[i])-b;}for(int i=1;i<=m;i++) {scanf("%d %d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(int i=1;i<=m;i++) {int ql=q[i].l,qr=q[i].r;while(l < ql) del(l++);while(r > qr) del(r--);while(l > ql) add(--l);while(r < qr) add(++r);ANS[q[i].id]=ans;}for(int i=1;i<=m;i++) printf("%d\n",-ANS[i]);return 0;
}

带修改的莫队

莫队本身是离线且不支持修改的，但我们可以把询问和修改操作分开记录，同时给修改打上时间戳，询问的结构体新开一个变量记录上一次修改的时间戳，然后指针移动的时候在时间维度也对齐即可。

在这里插入图片描述

P1903 [国家集训队]数颜色 / 维护队列

单点修改，询问区间不同的数的个数。带修莫队的板题。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 2e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定序列 单点修改 区间查询 每次查询[l,r]内不同数的个数
//给询问的结构体增加一个时间戳维度，保存本次询问上一次最近的修改时间
//指针移动的时候 在对齐区间之后  还需要对齐时间维度
struct node 
{int l,r,last,id;//last:当前询问的最近一次修改的时间戳
}q[maxn];
struct  
{int pos,val;
}C[maxn];//记录修改
int n,m,a[maxn],block;
int num[maxn*10];int ret,ans[maxn];//ret 目前的答案  
int cntq,cntc;//询问 修改的时间戳
inline bool cmp(const node &a,node b)
{if(a.l/block!=b.l/block)return a.l/block<b.l/block;if(a.r/block!=b.r/block)return a.r/block<b.r/block;return a.last<b.last; 
}
inline void del(int x) 
{if(--num[a[x]] == 0) ret--; 
}
inline void add(int x) 
{if(++num[a[x]] == 1) ret++;
}
inline void work(int now,int i) //进行第now次操作
{//C[t] 把pos位置的数 改成valif(q[i].l <= C[now].pos && C[now].pos <= q[i].r) //只有这个修改位于区间内部 才会造成影响 {if(--num[a[C[now].pos]] == 0) ret--;if(++num[C[now].val] == 1) ret++;}//这个操作以后可能还需要撤销 所以需要把两个地方的值交换一下 以后再交换1次就是撤销swap(C[now].val,a[C[now].pos]);
}
int main()
{scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=m;i++) {char s[10];int x,y;scanf("%s %d %d",s,&x,&y);if(s[0]=='Q') //询问和修改分开存 {q[++cntq].l=x,q[cntq].r=y;q[cntq].last=cntc;//最近一次修改的时间戳q[cntq].id=cntq;}else {C[++cntc].pos=x;C[cntc].val=y;}}block = pow(n,2.0 / 3.0);//块的大小 sort(q+1,q+cntq+1,cmp);int l=1,r=0,now=0;//now 表示当前进行了第几次修改for(re int i=1;i<=cntq;i++) {int ql=q[i].l,qr=q[i].r;//先对齐区间while(l < ql) del(l++);while(l > ql) add(--l);while(r < qr) add(++r);while(r > qr) del(r--);//再对齐时间while(now < q[i].last) work(++now,i);while(now > q[i].last) work(now--,i);ans[q[i].id]=ret;}for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]);return 0;
}

F. Machine Learning

题意：给定序列,有两种操作，单点修改和区间查询，每次查询[l,r]内的数出现次数的mex。

我们用num[i] 记录数i在当前区间出现的次数,cnt[i]记录出现i次的数的个数。
求mex的过程就遍历cnt[]即可，由等差数列和公式可知，求一次mex的时间复杂度是O（n^(1/2)）级别的，所以可以暴力用带修改的莫队。
时间复杂度为O(n ^(5/3))

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 2e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//给定序列 单点修改 区间查询 每次查询[l,r]内的数出现次数的mex
//给询问的结构体增加一个时间戳维度，保存本次询问上一次最近的修改时间
//指针移动的时候 在对齐区间之后  还需要对齐时间维度
//查询mex 可以暴力 是根号n的复杂度
int n,m,n0,block;
int a[maxn],b[maxn];//序列 离散化后的序列
int num[maxn],cnt[maxn];//i出现了多少次   出现i次的数有多少个  出现0次的数有无穷多个
struct node 
{int l,r,id,last;//last 上一次修改的时间戳
}q[maxn];
struct 
{int pos,val;
}C[maxn];
int cntq,cntc;
int ans[maxn];
inline bool cmp(const node &a,const node &b)
{if(a.l/block!=b.l/block)return a.l/block<b.l/block;if(a.r/block!=b.r/block)return a.r/block<b.r/block;return a.last<b.last; 
}
inline void del(int x) 
{//a[x]减1个cnt[num[a[x]]]--;cnt[--num[a[x]]]++;
}
inline void add(int x) 
{//a[x]加1个cnt[num[a[x]]]--;cnt[++num[a[x]]]++;
}
inline void work(int now,int i) //第i个询问 进行第now次修改
{int p=C[now].pos,v=C[now].val;if(q[i].l <= C[now].pos  &&  C[now].pos <= q[i].r) {cnt[num[a[p]]]--;cnt[--num[a[p]]]++;cnt[num[v]]--;cnt[++num[v]]++;}//这次修改以后可能会撤销  所以我们交换这两个地方的值 下次交换再交换就相当于撤销了swap(a[p],C[now].val);
}
inline void getmex(int x) 
{for(int i=1;i<=n+1;i++) {if(!cnt[i]){ans[x]=i;break;}}
}
int main()
{scanf("%d %d",&n,&m);block = pow(n,2.0 / 3.0);for(int i=1;i<=n;i++) {scanf("%d",a+i);b[i]=a[i];}for(int i=1;i<=m;i++) {int f,x,y;scanf("%d %d %d",&f,&x,&y);if(f == 1) {q[++cntq].l=x;q[cntq].r=y;q[cntq].id=cntq;q[cntq].last=cntc;}else {C[++cntc].pos=x;C[cntc].val=y;b[n+cntc]=y;}}//离散化sort(b+1,b+n+cntc+1);n0=unique(b+1,b+n+cntc+1)-b-1;for(int i=1;i<=n;i++) {a[i]=lower_bound(b+1,b+n0+1,a[i])-b;}for(int i=1;i<=cntc;i++) {C[i].val=lower_bound(b+1,b+n0+1,C[i].val)-b;}sort(q+1,q+cntq+1,cmp);int l=q[1].l,r=q[1].l-1,now=0;//now 目前修改已经进行了now次for(int i=1;i<=cntq;i++) {int ql=q[i].l,qr=q[i].r;while(l < ql) del(l++);while(l > ql) add(--l);while(r < qr) add(++r);while(r > qr) del(r--);while(now < q[i].last) work(++now,i);while(now > q[i].last) work(now--,i);getmex(q[i].id);}for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]);return 0;
}

树上莫队

莫队是用来解决区间问题的，而对于树上问题，如果是同一棵子树里的顶点问题，那可以用普通的dfs序来解决，否则，我们需要用欧拉序，把树上的简单路径变成一段连续的区间。
比如对于u到v两个节点来说，我们需要得到u到v简单路径上的一些信息，那么我们可以先dfs求出欧拉序，in[u]表示u第一次在欧拉序中出现的位置，out[u]表示第二次，我们不妨假设in[u]<in[v] ，如果u v存在祖孙关系，那么u到v路径经过的点就是[in[u],in[v]]内只出现过1次的点，如果不存在祖孙关系，那么就是[out[u],in[v]]内只出现1次的点，再加上u v的LCA。
简单点来说，我们利用欧拉序把树变成一个长度为2n的序列，每个元素都是树上的顶点编号，然后我们用莫队算法跑这个序列。

举例来说:

SPOJ - COT2

题意：给定带点权的树，m次询问，每次询问u v两个顶点简单路径上不同数的个数。

我们开结构体存查询，用lca这个变量记录查询的两个顶点的lca，当然如果存在祖孙关系则设为0。
预处理求出欧拉序（注意开两倍空间），可以树链剖分求出LCA
对查询的排序和普通的莫队一样
由于区间内出现两次的点不需要统计进去，我们可以开一个bool数组来标记，如果是0则表示顶点i加入，1表示删除，然后和1异或一下
有个地方注意就是，莫队始终是用指针移动维护区间信息的，所以加入LCA这个点的时候只是为了求出答案，完了还需把这个点删了。

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define ll long long
#define pii pair<int,int>
#define re register
const int maxn = 2e5+10;
const int mx = 40;
const int mod = 1e9+7;
const ll inf = 34359738370;
const int INF = 1e9+7;
const double pi = acos(-1.0);
//树上莫队  求带点权的树的2个顶点的简单路径之间 数的种类个数
//不能树链剖分 因为无法合并两条链的信息  普通的dfs序也无法把树压成这种特殊的区间
//欧拉序  对于一个子树的根节点 刚开始访问的时候扔进序列  结束访问的时候也扔进序列 
//对于顶点x y  假设in[x]<in[y],如果他们有祖孙关系 (LCA(x,y)==x) 那么x y路径上的点就是[in[x],in[y]]出现1次的点
//如果没有祖孙关系  [out[x],in[y]]区间上出现1次的点
// (但是这样会漏掉LCA 所以我们区间跑完后 还需要把LCA加入答案 计入之后再删去他的影响 因为我们维护的仅仅是欧拉序的区间 ) 
//证明的话 [in[x],out[x]]上的点都是x子树里面的 肯定不在x y的简单路径上 所以要减去
//欧拉序要开2倍空间
//由于出现2次的顶点不需要统计入答案 我们可以开一个vis[]标记每个顶点是否被访问过  0则加入 1则删除
struct 
{int to,next;
}e[maxn<<1];
int n,m,r;
int head[maxn],cnt;int a[maxn],b[maxn],n0;//离散化
int num[maxn];
int ans[maxn],ret=0;
struct node 
{int l,r,id,lca;//l/r:此查询对应在欧拉序中的左/右区间端点//lca  查询的两个顶点的lca  如果位于同一条链 则设为0
}q[maxn];
int block;
inline bool cmp(const node &a,const node &b) //奇偶排序
{return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}inline void add(int u,int v) 
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}int siz[maxn],fa[maxn],dep[maxn],son[maxn];
void dfs1(int rt,int par) 
{siz[rt]=1;dep[rt]=dep[par]+1;fa[rt]=par;for(int i=head[rt];i;i=e[i].next) {int to=e[i].to;if(to == par) continue;dfs1(to,rt);siz[rt]+=siz[to];if(siz[to] > siz[son[rt]]) son[rt]=to;}
}int pos[maxn],in[maxn],out[maxn],dft,top[maxn];
void dfs2(int rt,int t) 
{top[rt]=t;in[rt]=++dft;pos[dft]=rt;if(son[rt]) dfs2(son[rt],t);for(int i=head[rt];i;i=e[i].next) {int to=e[i].to;if(to != fa[rt] && to != son[rt]) {dfs2(to,to);}}//欧拉序 开始访问和结束访问需要收进序列out[rt]=++dft;pos[dft]=rt;
}int LCA(int x,int y) 
{int fx=top[x],fy=top[y];while(fx != fy) {if(dep[fx] < dep[fy]) swap(x,y),swap(fx,fy);//先跳链顶更深的那个x=fa[fx];fx=top[x];}//此时x y的链顶相等  说明在同一条链  深度小的就是LCAif(dep[x] < dep[y]) return x;return y;
}
bool vis[maxn];//i号顶点被访问的状态  0表示增加 1表示删除
inline void work(int x) //x是树节点编号
{if(!vis[x]) //增加这个节点{num[a[x]]++;if(num[a[x]]==1) ret++;}else {num[a[x]]--;if(!num[a[x]]) ret--;}vis[x]^=1;
}
int main()
{scanf("%d %d",&n,&m);block=sqrt(n);for(re int i=1;i<=n;i++) scanf("%d",a+i),b[i]=a[i];sort(b+1,b+n+1);n0 = unique(b+1,b+n+1)-b-1;for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n0+1,a[i])-b;//离散化for(int i=1;i<n;i++){int u,v;scanf("%d %d",&u,&v);add(u,v),add(v,u);}dfs1(1,1);dfs2(1,1);//树剖求LCAfor(int i=1;i<=m;i++) {int x,y;scanf("%d %d",&x,&y);q[i].id=i;if(in[x] > in[y]) swap(x,y);int L=LCA(x,y);if(L == x) {q[i].l=in[x];q[i].r=in[y];}else {q[i].l=out[x];q[i].r=in[y];q[i].lca=L;//只有这种情况需要加上LCA的贡献}}sort(q+1,q+m+1,cmp);int l=q[1].l,r=q[1].l-1;for(int i=1;i<=m;i++) {int ql=q[i].l,qr=q[i].r;while(l < ql) work(pos[l++]);while(l > ql) work(pos[--l]);while(r < qr) work(pos[++r]);while(r > qr) work(pos[r--]);if(q[i].lca) work(q[i].lca);ans[q[i].id]=ret;if(q[i].lca) work(q[i].lca);}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}