# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are given a tree of n vertices. Each vertex contains an integer. Vertex 1 is the root of the tree, each of the n-1 remaining vertices has a parent in the tree. A vertex is connected with its parent by an edge. The parent of vertex i is vertex p_{i}. The parent index is always less than the index of the vertex (i.e., p_{i} < i).

We say that vertex u is in the sub-tree of vertex v, if we can get from u to v, moving from the vertex to the parent. In particular, vertex v is in its sub-tree.

You will be given m queries, the i^{th} of which consists of two numbers: v and x. You need to find out how many of vertices of sub-tree v consists value greater than or equal to x, that means a_{u} ≥ x, where vertex u is in the sub-tree of vertex v.

The first line contains two integers **n** and **m** (1 ≤ n, m ≤ 5 × 10^{5}), the number of nodes in the tree and queries, respectively.

The following line contains n-1 integers **p _{2}, p_{3},… , p_{n}** (1 ≤ p

The next line contains n integers, the i^{th} of these integers **a _{i}** (1 ≤ a

The next **m** lines describe the queries, the i^{th} line contains two numbers **v** (1 ≤ v ≤ n) and **x** (1 ≤ x ≤ 10^{9}), the vertex and the depth that appear in the i^{th} query.

For each query, print the number of vertices of sub-tree v consists value greater than or equal to x.

Input | Output |
---|---|

3 2 1 2 5 6 7 1 3 1 6 | 3 2 |

90% Solution Ratio

fsshakkhorEarliest,

moshiur_cse15Fastest, 0.5s

sarwarITLightest, 47 MB

SoudipShortest, 723B

Login to submit

This problem can be solved with BIT or Merge Sort Tree after constructing the required array using D...