Practice on Toph

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

Tree Queries

By emrul_mu · Limits 2s, 512 MB

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



90% Solution Ratio

fsshakkhorEarliest, Apr '19

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