Selective Selective Cutting

View as PDF

Submit solution

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

Problem types

I have 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.