## Selective Selective Cutting

View as PDF

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

Author:
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$$?".

#### Constraints

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

3
2

#### 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$$.