## Another Contest 8 Problem 4 - Up and Down

View as PDF

Points: 15
Time limit: 0.5s
Memory limit: 512M

Problem type

Brandon likes to go up and down. Brandon has a tree rooted at vertex . The root is at depth zero, and the depth of any non-root node is one more than the depth of its parent. Therefore, all node depths are nonnegative.

Brandon wants to know, for ordered pairs of positive integers , how many ordered pairs of vertices have a shortest path that involves going up the rooted tree by exactly vertices and then going down the rooted tree by exactly vertices. When going up the tree, the depth of vertices decreases. When going down the tree, the depth of vertices increases.

#### Constraints

No pair will appear more than once.

#### Input Specification

Each test case starts with a line containing a single positive integer, . The next lines contain two positive integers, and , indicating those two vertices are connected by an edge. It is guaranteed that the provided graph is a tree.

After that, a line containing a single positive integer, , is given. The next lines contain two positive integers, and , representing a query. Brandon wishes to count the number of ordered pairs of vertices that have a shortest path that involves going up the rooted tree by vertices and then going down the rooted tree by vertices.

#### Output Specification

Output lines in order, the answers to the given queries.

#### Sample Input

5
5 2
1 5
5 3
3 4
3
1 2
2 1
2 2

#### Sample Output

1
1
0