Spoj 10707 Count on a tree II

给定一棵包含 $N$ 个节点的树，每个节点都有一个权值。你需要回答 $M$ 次询问。

每次询问给出两个整数 $u,v$，实际询问的两个节点为 $u\mathbin{\mathrm{xor}}\mathrm{lastans}$ 和 $v$，其中 $\mathrm{lastans}$ 表示上一次询问的答案，初始值为 $0$。对于每次询问，求这两个节点之间的简单路径上共有多少种不同的节点权值。

输入格式

第一行包含两个整数 $N,M$，分别表示树的节点数和询问数。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示节点 $i$ 的权值。

接下来 $N-1$ 行，每行包含两个整数 $x,y$，表示节点 $x$ 与节点 $y$ 之间有一条边。

最后 $M$ 行，每行包含两个整数 $u,v$，表示一组经过异或加密的询问。

输出格式

输出共 $M$ 行，每行一个整数，表示对应询问路径上不同节点权值的种数。

样例输入

8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8

样例输出

4
4

数据范围

• $N\le 4\times 10^4$；
• $M\le 10^5$；
• 节点权值在 int 类型的取值范围内；
• 时间限制为 $2\times 10^4\ \mathrm{ms}$；
• 内存限制为 $409600\ \mathrm{KB}$。

来源与许可

本题为 SPOJ 10707「Count on a tree II」，题面与测试数据整理自 BZOJ 2589。

样例 1

输入

8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8

输出

4
4