Subtree K Th Max :
Difficulty Level : Medium
Submissions : 266
Asked In :
Marks :15
: 9 | : 0
We have a rooted tree with $$$n$$$ vertices. The vertices are numbered $$$1$$$ through $$$n$$$, and the root is Vertex $$$1$$$. The $$$i^{th}$$$ edge connects Vertices $$$u$$$ and $$$v$$$. Vertex $$$i$$$ has an integer $$$x_i$$$ written on it.
You need to answer $$$q$$$ queries of the following types:
- $$$v$$$ $$$k$$$ — among the integers written on the vertices in the subtree rooted at Vertex $$$v$$$, find the $$$k-th$$$ largest value.
The first line of input contains two space separated integers $$$n$$$ $$$(1 \le n \le 10^5)$$$ and $$$q$$$ $$$(1 \le q \le 10^5)$$$.
The second line contains $$$n$$$ space separated integers $$$x_1,x_2,...x_n$$$ $$$(1 \le x_i \le 10^9)$$$— $$$x_i$$$ represents the value on node $$$i$$$ respectively.
The next $$$n-1$$$ lines contain two space separated integers $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ each denoting an edge between vertices $$$u$$$ and $$$v$$$.
Finally, the next $$$q$$$ lines contain two space separated integers $$$x$$$ $$$(1 \le x \le n)$$$ and $$$k$$$ $$$(1 \le k \le 20)$$$ each denoting the queries.
Print the answer to each query in a single line.
5 2 1 2 3 4 5 1 4 2 1 2 5 3 2 1 2 2 1
4 5
6 2 10 10 10 9 8 8 1 4 2 1 2 5 3 2 6 4 1 4 2 2
9 10
4 4 1 10 100 1000 1 2 2 3 3 4 1 4 2 3 3 2 4 1
1 10 100 1000
For sample test case $$$1$$$, the tree given in this input is shown below.
- For the $$$1^{st}$$$ query, the vertices in the subtree rooted at Vertex $$$1$$$ are Vertices $$$1,2,3,4,$$$ and $$$5$$$, so print the $$$2^{nd}$$$ largest value of the numbers written on these vertices — $$$4$$$.
- For the $$$2^{nd}$$$ query, the vertices in the subtree rooted at Vertex $$$2$$$ are Vertices $$$2,3,$$$ and $$$5$$$, so print the $$$1^{st}$$$ largest value of the numbers written on these vertices — $$$5$$$.
