题目大意：有一棵$n$个节点的树，第$i$个点有一个颜色$C_i$，$m$组询问，每次问$x->y$的路径上有多少种颜色
题解：树上莫队，把树按欧拉序展开成一条链，令第$i$个节点第一次出现在序列中为$in_i$，第二次为$out_i$，每一个询问就是看$in_x->in_y$中只出现一次的节点的颜色，但发现如果$x$不为$x,y$的$lca$的话$lca$不会被计入答案，特判一下就行
卡点：1$\sim$2.数组未开大
3.$tarjan$求$lca$时加询问加错
4.为先加入第一个点导致答案多一
C++ Code：
#include <cstdio>
#include <algorithm>
#define maxn 40010
#define maxm 100010
#define N (maxn << 1)
#define bl(x) ((x) >> 9)
int n, m;
int in[maxn], out[maxn], date[N], idx;
struct Query {
int l, r, lca, id;
bool addlca;
inline bool operator < (const Query &rhs) const {
return (bl(l) == bl(rhs.l)) ? r < rhs.r : l < rhs.l;
}
} q[maxm];
namespace tree {
int head[maxn], cnt = 0;
struct Edge {
int to, nxt;
} e[maxn << 1];
inline void add(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt;
}
int fa[maxn]; void dfs(int u) {
date[in[u] = ++idx] = u;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != fa[u]) {
fa[v] = u;
dfs(v);
}
}
date[out[u] = ++idx] = u;
}
}
namespace tarjan {
int head[maxn], cnt = 0;
struct QUERY {
int v, nxt, id;
} Q[maxm << 1];
inline void add(int a, int b, int c) {
Q[++cnt] = (QUERY) {b, head[a], c}; head[a] = cnt;
Q[++cnt] = (QUERY) {a, head[b], c}; head[b] = cnt;
} int f[maxn];
inline void init(int n) {
for (int i = 1; i <= n; i++) f[i] = i;
}
int find(int x) {return (x == f[x] ? x : (f[x] = find(f[x])));} bool vis[maxn];
void dfs(int u) {
for (int i = tree::head[u]; i; i = tree::e[i].nxt) {
int v = tree::e[i].to;
if (v != tree::fa[u]) {
dfs(v);
f[v] = u;
}
}
for (int i = tarjan::head[u]; i; i = tarjan::Q[i].nxt) q[Q[i].id].lca = find(Q[i].v);
}
}
#define ONLINE_JUDGE
#include <cctype>
namespace R {
int x;
#ifdef ONLINE_JUDGE
char *ch, op[1 << 26];
inline void init() {
fread(ch = op, 1, 1 << 26, stdin);
}
inline int read() {
while (isspace(*ch)) ch++;
for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15);
return x;
}
#else
char ch;
inline int read() {
ch = getchar();
while (isspace(ch)) ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x;
}
#endif
} inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
int num[maxn], W[maxn], w[maxn], ans[maxm];
bool vis[maxn];
int main() {
#ifdef ONLINE_JUDGE
R::init();
#endif
tarjan::init(n = R::read()); m = R::read();
for (int i = 1; i <= n; i++) W[i] = w[i] = R::read();
int tot = (std::sort(W + 1, W + n + 1), std::unique(W + 1, W + n + 1) - W - 1);
for (int i = 1; i <= n; i++) w[i] = std::lower_bound(W + 1, W + tot + 1, w[i]) - W;
for (int i = 1; i < n; i++) tree::add(R::read(), R::read());
tree::dfs(1);
for (int i = 1; i <= m; i++) tarjan::add(q[i].l = R::read(), q[i].r = R::read(), q[i].id = i);
tarjan::dfs(1);
for (int i = 1; i <= m; i++) {
int &l = q[i].l, &r = q[i].r;
if (in[l] > in[r]) swap(l, r);
l = (q[i].addlca = (q[i].lca != l)) ? out[l] : in[l];
r = in[r];
}
std::sort(q + 1, q + m + 1);
int l, r, res; l = 1, r = 1, res = 1;
vis[date[1]] = 1; num[w[date[1]]]++;
for (int i = 1; i <= m; i++) {
while (l > q[i].l) (vis[date[--l]] ^= 1) ? (res += num[w[date[l]]]++ == 0) : (res -= --num[w[date[l]]] == 0);
while (r < q[i].r) (vis[date[++r]] ^= 1) ? (res += num[w[date[r]]]++ == 0) : (res -= --num[w[date[r]]] == 0);
while (l < q[i].l) (vis[date[l]] ^= 1) ? (res += num[w[date[l++]]]++ == 0) : (res -= --num[w[date[l++]]] == 0);
while (r > q[i].r) (vis[date[r]] ^= 1) ? (res += num[w[date[r--]]]++ == 0) : (res -= --num[w[date[r--]]] == 0);
ans[q[i].id] = res + (q[i].addlca && !num[w[q[i].lca]]);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}