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



91% Solution Ratio

fsshakkhorEarliest, Apr '19

zefferskioich.338316Fastest, 0.4s

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

Toph uses cookies. By continuing you agree to our Cookie Policy.