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 pi. The parent index is always less than the index of the vertex (i.e., pi < 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 ith 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 au ≥ 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 × 105), the number of nodes in the tree and queries, respectively.
The following line contains n-1 integers p2, p3,… , pn (1 ≤ pi < i), the parents of vertices from the second to the nth.
The next line contains n integers, the ith of these integers ai (1 ≤ ai ≤ 109) is written on vertex i.
The next m lines describe the queries, the ith line contains two numbers v (1 ≤ v ≤ n) and x (1 ≤ x ≤ 109), the vertex and the depth that appear in the ith query.
For each query, print the number of vertices of sub-tree v consists value greater than or equal to x.
3 2 1 2 5 6 7 1 3 1 6
Login to submit
This problem can be solved with BIT or Merge Sort Tree after constructing the required array using D...