树上的频率查询AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)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$ 的个数。
- 设在连接顶点
$s$和顶点$t$的路径上的顶点中，写有整数$y$的顶点数量为$f$。则满足$a \leq f \leq b$。
Constraints
约束条件
AI (CI翻译)$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.
$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$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入给出，格式如下：AI (CI翻译)
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}_QN 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}_QEach query $\mathrm{query}_q$ is given in the following format:
每次查询 $\mathrm{query}_q$ 的格式如下：AI (CI翻译)
s t a bs t a bOutput
输出格式
AI (CI翻译)Output $Q$ lines. The $q$-th line should contain the answer to the $q$-th query.
输出 $Q$ 行。第 $q$ 行应包含第 $q$ 次查询的答案。AI (CI翻译)
样例
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
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
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。