All Tracks Data Structures Trees Problem

The Unstable Root
Tag(s):

Centroid Decomposition, Data Structures, Lowest Common Ancestor, Medium-Hard, Trees

Problem
Editorial
Analytics

You are given a tree comprising \(n\) nodes numbered from \(1\) to \(n\). You have to answer \(q\) queries each consisting of three numbers – \(r\)\(d_1\) and \(d_2\)

For each query, print the number of nodes whose depth is between \(d_1\) and \(d_2\) (inclusive) if the tree is rooted at node \(r\). The depth of root node itself is \(0\), the depth of all its children is \(1\) and so on.

Input format

First line: \(n\) (the number of nodes) and \(q\) (the number of queries)

Next \(n-1\) lines: \(u_i\) and \(v_i\)denoting an edge between the nodes \(u_i\) and \(v_i\).The next \(q\) lines consist of three integers \(r\)\(d_1\) and \(d_2\) .

Output format

For each query, print the answer in a new line.

input Constraints

\(1 \le n \le 100000\\1 \le q \le 150000\\ 0 \le d_1 \le d_2 \le n\\1 \le r \le n\)

 

SAMPLE INPUT
5 2
1 2
1 3
2 4
4 5
1 0 2
2 0 1
SAMPLE OUTPUT
4
3
Explanation

For node 1, there are 4 nodes whose depth is between 0 and 2 (1,2,3 and 4). For node 2 there are 3 nodes whose depth is between 0 and 1 (1,2 and 4).

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?