The Unstable Root
Tag(s):

## Centroid decomposition, Data Structures, Loops, Medium-Hard, Tree

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

## This Problem was Asked in Challenge Name

November Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > String Algorithms
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > Advanced Algorithms