ADABERRY - Ada and Mulberry

Ada the Ladybug grows a mulberry tree (which is rooted at node 0). At the beginning, it has a mulberry fruit of distinct size growing on every node. As the time flows, new mulberry fruits appear on each node (additionally - meaning the previous mulberry fruit still remains on given node) - while keeping the condition of distinct sizes.

Ada observes every single fruit and for each new fruit she is asking you to tell her the number of lesser fruits in the subtree of given node.

Input

The first line contains two integers 1 ≤ N, Q ≤ 2*105 , size of mulberry tree.

The next line contains N integers: 0 ≤ Ai ≤ 106, the size of mulberry fruit in each node.

Each of the next N-1 lines contains two integers 0 ≤ a, b < N, meaning the branch (edge) between given nodes.

Each of the next Q lines contains two integers a S: 0 ≤ a < N (the node in which new fruit grows) and 0 ≤ S ≤ 106 (size of the fruit)

Output

For each query, print the number of lesser mulberry fruits which grow in subtree of node where new mulberry fruit grew.

Example Input

7 8
10 9 13 17 11 20 18
0 4
0 1
1 2
1 3
2 5
2 6
0 21
0 8
2 15
3 22
1 14
2 19
0 12
1 16

Example Output

7
0
1
1
2
3
4
4

Added by:Morass
Date:2017-03-05
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-11-27 15:26:13 Buda IM (retired)
Cool problem, took me a while to take the GOlang solution to the promise land
2023-01-20 14:22:31
Probably the judge set is changed. Even i directly copy the accepted code of another but it still shows TLE. Please can you check the test set?
My TLE code: <snip>
Accepted code: <snip>
[Simes]: This isn't the place for coding discussions, use the forum

Last edit: 2023-01-20 22:51:32
2018-10-06 22:35:59
Nice one AC in one go
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.