AT_abc477_g.Frequency Query on Tree

You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertex $u_i$ and vertex $v_i$. Also, integer $x_i$ is written on vertex $i$.
Process $Q$ queries. In each query, you are given integers $s,t,a,b$; find the number of integers $y$ satisfying the following condition.

• Let $f$ be the number of vertices with integer $y$ written on them among the vertices on the path connecting vertex $s$ and vertex $t$. Then, $a \leq f \leq b$ holds.

给你一棵包含 $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$。

The input is given from Standard Input in the following format:

$N$ $Q$
$x_1$ $x_2$ $\dots$ $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$

Each query $\mathrm{query}_q$ is given in the following format:

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

输入从标准输入中按以下格式给出：

$N$ $Q$
$x_1$ $x_2$ $\dots$ $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$

Output $Q$ lines. The $q$-th line should contain the answer to the $q$-th query.

输出 $Q$ 行。第 $q$ 行应包含第 $q$ 个查询的答案。

Sample 1 Explanation:
Consider the first query.
The vertices on the path connecting vertex $1$ and vertex $5$ are, in order, vertex $1$, vertex $2$, vertex $3$, vertex $4$, and vertex $5$.
The integers written on these vertices are, in order, $1, 2, 3, 1, 2$. Thus, there are three integers $y$ satisfying the condition: $1,2,3$.

Constraints

• $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$
• The given graph is a tree.
• $1 \leq x_i \leq N$
• $1 \leq s \lt t \leq N$
• $1 \leq a \leq b \leq N$
• All input values are integers.

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

约束条件

• $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$
• 所有输入值均为整数。