P17697 颜色

题目来源：【HT-129-Div.1】核桃省选模拟赛

有一棵 $n$ 个点的树，每个点上写着点权 $a_i$。称 $u$ 到 $v$ 的简单路径是好的，当且仅当这条简单路径上的点权两两不同。有 $q$ 次询问，每次给定两个点 $u,v$，求 $u$ 到 $v$ 的路径中有多少子路径是好的。

第一行两个正整数 $n,q$ 表示树的点数和询问次数。 接下来一行 $n$ 个正整数表示 $a_1,a_2,\cdots,a_n$。 接下来 $n-1$ 行，每行两个正整数 $u,v$，表示树上的一条无向边 $u,v$。 接下来 $q$ 行，每行两个正整数 $u,v$ 表示询问的路径。

输出 $q$ 行，每行输出一个整数表示答案。

**本题采用子任务捆绑测试。** | 子任务编号 | $n\leq$ | $q \leq$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:|:-:| | $1$ | $100$ | $100$ | 无 | $5$ | | $2$ | $5 \times 10^3$ | $5 \times 10^3$ | 无 | $15$ | | $3$ | $5 \times 10^4$ | $5 \times 10^4$ | 无 | $20$ | | $4$ | $10^5$ | $10^5$ | 树构成一条链 | $20$ | | $5$ | $10^5$ | $10^5$ | $a_i$ 在 $[1,n]$ 之间的正整数中均匀随机生成 | $10$ | | $6$ | $10^5$ | $10^5$ | 无 | $30$ | 对于 $100\%$ 的数据，保证 $1 \leq n,q \leq 10^5$，$1 \leq a_i \leq n$。