题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 与顶点 $v_i$。此外，顶点 $i$ 上写着整数 $x_i$。

请处理 $Q$ 个询问。每个询问给出整数 $s,t,a,b$，求满足以下条件的整数 $y$ 的个数。

• 设 $f$ 为「连接顶点 $s$ 与顶点 $t$ 的路径上的顶点中，写着整数 $y$ 的顶点个数」。此时 $a \leq f \leq b$ 成立。

输入格式

输入按以下格式从标准输入读入：

• $N$ $Q$
• $x_1$ $x_2$ $\ldots$ $x_N$
• $u_1$ $v_1$
• $u_2$ $v_2$
• $\vdots$
• $u_{N-1}$ $v_{N-1}$
• $\mathrm{query}_1$
• $\mathrm{query}_2$
• $\vdots$
• $\mathrm{query}_Q$

每个询问 $\mathrm{query}_q$ 按以下格式给出：

• $s$ $t$ $a$ $b$

输出格式

输出 $Q$ 行。第 $q$ 行是第 $q$ 个询问的答案。

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

3
1
3
0

考虑第 1 个询问。连接顶点 $1$ 与顶点 $5$ 的路径上的顶点依次为顶点 $1$、顶点 $2$、顶点 $3$、顶点 $4$、顶点 $5$。写在这些顶点上的整数依次为 $1, 2, 3, 1, 2$。因此，满足条件的整数 $y$ 共有三个：$1,2,3$。

11 8
1 2 3 1 4 2 2 5 2 1 2
1 2
1 3
2 4
1 5
4 6
6 7
3 8
7 9
4 10
9 11
8 11 3 5
6 10 1 5
8 9 5 6
1 11 1 4
4 6 2 5
5 6 2 6
3 7 1 1
5 7 5 8

1
2
0
1
0
2
1
0

数据范围

• $2 \leq N \leq 2 \times 10^5$

• $1 \leq Q \leq 2 \times 10^5$

• $1 \leq u_i \lt v_i \leq N$

• 给定的图是一棵树。

• $1 \leq x_i \leq N$

• $1 \leq s \lt t \leq N$

• $1 \leq a \leq b \leq N$

• 所有输入值均为整数。

• 来源：AtCoder ABC 477 G

子任务设置

• 子任务 1（30 分）：$N, Q \le 2000$。
• 子任务 2（30 分）：树是一条链（$u_i = i$，$v_i = i + 1$），且 $N, Q \le 2 \times 10^5$。
• 子任务 3（40 分）：无特殊限制。