DMPG '18 G3 - Lonely Carrot's Anguish

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The land of carrot trees is a magical land tree with N nodes and N-1 edges, rooted at node 1. One day, a lonely carrot decides to ask Q queries of the form n d: the number of unordered pairs of nodes that have a depth between \operatorname{depth}(n) and \operatorname{depth}(n)+d have node n as their lowest common ancestor. Note that these pairs may include the node n itself and the pair may be two of the same node. Also note that this d can be larger than the height of the subtree from n. Can you help the poor carrot with these queries?

Note: The lowest common ancestor of nodes u and v is the furthest node from the root that is on the path from u to the root and on the path from v to the root.

Constraints

For all subtasks, 1 \le a_i, b_i \le N and 1 \le n_i \le N.

Subtask 1 [10%]

1 \le N \le 200\,000
1 \le Q \le 200\,000
d_i = N

Subtask 2 [20%]

1 \le N \le 2\,000
1 \le Q \le 2\,000
0 \le d_i \le N

Subtask 3 [70%]

1 \le N \le 200\,000
1 \le Q \le 200\,000
0 \le d_i \le N

Input Specification

The first line will have N, the number of nodes.
The next N-1 lines will have two integers, a_i and b_i, indicating that there is an edge from a_i to b_i.
The next line will have Q, the number of queries that follow.
The next Q lines will have two space separated integers, n_i and d_i, the n and d values for the i^{\text{th}} query.

Output Specification

The answer to each query, each on a new line.

Sample Input

10
1 2
1 3
4 2
5 2
6 2
7 3
8 3
9 5
10 6
5
1 4
1 3
2 1
2 2
1 2

Sample Output

28
28
7
14
20

Explanation for Sample

For the third query for example, the 7 unordered pairs are (2, 2), (2, 4), (2, 5), (2, 6), (4, 5), (4, 6), (5, 6).


Comments

There are no comments at the moment.