算法简介：重帘留香

树上莫队，就是字面意思上的树上的莫队，但实际上，一般来讲的树上莫队指的都是用欧拉序把一棵树压成数组，然后对其进行普通莫队的操作。

算法演示：天青现虹

算法推导：织诗成锦

那么首先我们可以随便画一棵树

然后我们首先手动算一算他的欧拉序。应该是 $[1,2,4,5,5,6,6,7,7,4,2,3,3,1]$ 。

那么我们考虑如果我们需要查询一个路径 $5-4-2-1-3$ ，会发生什么事。那么首先把他转化成欧拉序上的一段，也就是 5 的最后一次出现位置，和 3 的第一次出现位置，那么把它所对应的那一段截取下来就应该是：$[5,6,6,7,7,4,2,3$] ，观察，我们发现这个路径上的点，在这段内容中，多了 6 和 7 但是他们出现次数都是偶数，不难想到用异或或者 vis 去重可以得到，其次是 1 号点，1 号点是 LCA 我们应该需要特殊计算。所以说大概的找找规律，可以知道大概的计算方式。接着就是按照这样的规则模拟即可。

最后有一个细节问题，欧拉序的大小是原来的两倍！

例题讲解：孤舟斩蛟

这里提供一道非常非常模板的题目：SP10707

就是在上述板子的基础上统计一波颜色即可。

// #pragma GCC optimize(2)
// #pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 4e4 + 10;
const int M = 1e5 + 10;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, Q, B;
int a[N];
Graph< N, N << 1 > G;
struct Qiz {
    int l, r, id, z;
    inline bool operator < (const Qiz& you) const {
        if(l / B != you.l / B) return l < you.l;
        return (((l / B) & 1) ? r < you.r : r > you.r);
    }
}qs[M];

vector<int >c;

inline void Input() {
    read(n, Q);
    for(int i = 1; i <= n; i++) read(a[i]), c.push_back(a[i]);
    int u, v;
    for(int i = 1; i < n; i++) {
        read(u, v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
    for(int i = 1; i <= Q; i++) {
        read(qs[i].l, qs[i].r); qs[i].id = i;
    }
}

int sz[N], sn[N], dep[N], tp[N], fa[N];
int in[N], ot[N], cntd, mp[N << 1];

void Dfs(int u, int FA) {
    dep[u] = dep[FA] + 1; sz[u] = 1; 
    in[u] = ++cntd; mp[cntd] = u;
    fa[u] = FA;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int  v = G.to(i);
        if(v == FA) continue;
        Dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[sn[u]]) sn[u] = v;
    }
    ot[u] = ++cntd; mp[cntd] = u;
}

void Dfs2(int u, int to) {
    tp[u] = to;
    if(sn[u]) Dfs2(sn[u], to);
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == sn[u] || v == fa[u]) continue;
        Dfs2(v, v);
    }
}

inline int LCA(int u, int v) {
    while(tp[u] != tp[v]) {
        if(dep[tp[u]] < dep[tp[v]]) swap(u, v);
        u = fa[tp[u]];
    }
    if (dep[u] > dep[v])swap(u, v);
    return u;
}

inline void Init() {
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
        // cout << a[i] << ' ';
    }
    // cout << endl;
    B = sqrt(n * 2); int u, v;
    for(int i = 1; i <= Q; i++) {
        u = qs[i].l, v = qs[i].r;
        if(in[u] > in[v]) swap(u, v);
        qs[i].id = i; qs[i].z = LCA(u, v);
        if(qs[i].z == u) {
            qs[i].l = in[u]; 
            qs[i].r = in[v];
            qs[i].z = 0;
        }
        else {
            qs[i].l = ot[u];
            qs[i].r = in[v];
        }
    }
}

int ans[M], res;
int vis[N], cnt[N];

inline void Upd(int x) {
    if(!vis[x]) {
        cnt[a[x]]++;
        if(cnt[a[x]] == 1) res++;
    }
    else {
        cnt[a[x]]--;
        if(cnt[a[x]] == 0) res--;
    }
    vis[x] ^= 1;
}

inline void Work() {
    Dfs(1, 0); Dfs2(1, 0); Init();
    // for(int i = 1; i <= n; i++) {
    //     cout << dep[i] << ' ' << fa[i] << ' ' << sz[i] << ' ' << sn[i] << endl;
    // }
    sort(qs + 1, qs + Q + 1);
    for(int i = 1, l = 1, r = 0; i <= Q; i++) {
        // cout << qs[i].l << ' ' << qs[i].r << ' ' << qs[i].z << ' ' << qs[i].id << '\n';
        while(l > qs[i].l) Upd(mp[--l]);
        while(r < qs[i].r) Upd(mp[++r]);
        while(l < qs[i].l) Upd(mp[l++]);
        while(r > qs[i].r) Upd(mp[r--]);
        if(qs[i].z) Upd(qs[i].z);
        ans[qs[i].id] = res;
        if(qs[i].z) Upd(qs[i].z);
    }
    // cout << endl;
    for(int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}