G - Frequency Query on Tree 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 625 点

問題文

頂点に 1 から N の番号がついた N 頂点の木が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。また、頂点 i には整数 x_i が書かれています。
Q 個のクエリを処理してください。クエリでは整数 s,t,a,b が与えられるので、以下の条件を満たす整数 y の個数を求めてください。

  • 頂点 s と頂点 t を結ぶパス上にある頂点のうち、整数 y が書かれた頂点の個数を f とする。この時、a \leq f \leq b が成り立つ。

制約

  • 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
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

Q 行出力せよ。q 行目には q 番目のクエリの答えを出力せよ。

入力例 1

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

出力例 1

3
1
3
0

1 番目のクエリを考えます。
頂点 1 と頂点 5 を結ぶパス上の頂点は順に頂点 1、頂点 2、頂点 3、頂点 4、頂点 5 です。
各頂点に書かれている整数は順に 1, 2, 3, 1, 2 です。よって、条件を満たす整数 y は 1,2,3 の 3 個です。

入力例 2

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

出力例 2

1
2
0
1
0
2
1
0

Score : 625 points

Problem Statement

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.

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.

Input

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

Output

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

Sample Input 1

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

Sample Output 1

3
1
3
0

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.

Sample Input 2

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

Sample Output 2

1
2
0
1
0
2
1
0