Selective Selective Cutting

View as PDF

Submit solution

Points: 20
Time limit: 2.0s
Memory limit: 256M

Problem types

There is a bidirectional unweighted connected graph with N nodes, numbered from 1 to N, each with a value a_i.

There are exactly N - 1 edges. The i^{\text{th}} edge connects u_i and v_i. There is at most one edge between any pair of nodes. No edge connects a node with itself.

Q questions are asked in the form: "On the path from u_j to v_j, including these u_j and v_j themselves, how many nodes have a value of at least k_j?".


All numbers in the input are positive integers.

1 \leq N, Q \leq 10^5

1 \leq a_i, k_j \leq 10^9

Input Specifications

All numbers on the same line of input are separated by spaces.

The first line of input contains 2 numbers: N and Q.

The second line of input contains N numbers, the i^{\text{th}} number is a_i.

The next N - 1 lines each contain 2 numbers: u_i and v_i.

The next Q lines contain 3 numbers: u_j, v_j, and k_j.

Output Specification

Q lines each containing one number, the j^{\text{th}} line representing the answer to the j^{\text{th}} question.

Sample Input 1

5 2
10 20 30 40 50
1 2
1 3
2 4
2 5
3 4 20
4 5 30

Sample Output 1


Explanation for Sample 1

The path from 3 to 4 is 3 \to 1 \to 2 \to 4. Out of these 4 trees, 3 of them have a height of at least 20.

The path from 4 to 5 is 4 \to 2 \to 5. Out of these 3 trees, 2 of them have a height of at least 30.


There are no comments at the moment.