## DMPG '18 G3 - Lonely Carrot's Anguish

View as PDF

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 nodes and edges, rooted at node . One day, a lonely carrot decides to ask queries of the form n d: the number of unordered pairs of nodes that have a depth between and have node as their lowest common ancestor. Note that these pairs may include the node itself and the pair may be two of the same node. Also note that this can be larger than the height of the subtree from . Can you help the poor carrot with these queries?

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

#### Input Specification

The first line will have , the number of nodes.
The next lines will have two integers, and , indicating that there is an edge from to .
The next line will have , the number of queries that follow.
The next lines will have two space separated integers, and , the and values for the 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 unordered pairs are .