题目描述

神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个 $1$ 到 $n$ 之间的正整数来表示一种颜色。树上一共有 $n$ 个苹果。每个苹果都被编了号码，号码为一个 $1$ 到 $n$ 之间的正整数。我们用 $0$ 代表树根。只会有一个苹果直接根。

有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为 $u$ 的苹果出发，由树枝走到编号为 $v$ 的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果 $u$ 和苹果 $v$ 的颜色）？不过神犇注意到，有些来膜拜的人患有色盲症。具体地说，一个人可能会认为颜色 $a$ 就是颜色 $b$ ，那么他们在数苹果的颜色时，如果既出现了颜色 $a$ 的苹果，又出现了颜色 $b$ 的苹果，这个人只会算入颜色 $b$ ，而不会把颜色 $a$ 算进来。

神犇是一个好人，他不会强人所难，也就会接受由于色盲症导致的答案错误（当然答案在色盲环境下也必须是正确的）。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟，但是他想考验一下你。你能替神犇完成这项任务吗？

输入格式

输入第一行为两个整数 $n$ 和 $m$，分别代表树上苹果的个数和前来膜拜的人数。

接下来的一行包含 $n$ 个数，第 $i$ 个数代表编号为 $i$ 的苹果的颜色 $Col_i$。

接下来有 $n$ 行，每行包含两个数 $x$ 和 $y$，代表有一根树枝连接了苹果 $x$ 和 $y$（或者根和一个苹果）。

接下来有m行，每行包含四个整数 $u,v,a,b$，代表这个人要数苹果 $u$ 到苹果 $v$ 的颜色种数，同时这个人认为颜色 $a$ 就是颜色 $b$。如果 $a=b=0$，则代表这个人没有患色盲症。

输出格式

输出一共 $m$ 行，每行仅包含一个整数，代表这个人应该数出的颜色种数。

5 3
1 1 3 3 2
0 1
1 2
1 3
2 4
3 5
1 4 0 0
1 4 1 3
1 4 1 2

2
1
2

数据规模与约定

对于 $100\%$ 的数据，$n \le 5 \times 10^4$，$m \le 10^5$，$0 \le x,y,a,b \le n$，$1 \le u,v,Col_i \le n$。

此题存在版权，故原 BZOJ 不再支持提交，保留在此只供大家参考题面！ 望见谅！