Ex - Sum of Min of Length Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木が与えられます。頂点には 1 から N までの番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。

また、この木における頂点 x と頂点 y の距離を d(x,y) で表します。ただし、頂点 x と頂点 y の距離とは、頂点 x から頂点 y までの最短パス上の辺の本数のことをいいます。

Q 個のクエリが与えられるので、順番に答えてください。i 番目のクエリは以下で説明されます。

  • 整数 L_i, R_i が与えられます。 \displaystyle\sum_{j = 1}^{N} \min(d(j, L_i), d(j, R_i)) の値を求めてください。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i, B_i, L_i, R_i \leq N
  • 与えられるグラフは木
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
Q
L_1 R_1
\vdots
L_Q R_Q

出力

Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。

入力例 1

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

出力例 1

4
6
3

1 番目のクエリについて説明します。
d(1, 4) = 2、d(1, 1) = 0 より \min(d(1, 4), d(1, 1)) = 0 です。
d(2, 4) = 2、d(2, 1) = 2 より \min(d(2, 4), d(2, 1)) = 2 です。
d(3, 4) = 1、d(3, 1) = 3 より \min(d(3, 4), d(3, 1)) = 1 です。
d(4, 4) = 0、d(4, 1) = 2 より \min(d(4, 4), d(4, 1)) = 0 です。
d(5, 4) = 1、d(5, 1) = 1 より \min(d(5, 4), d(5, 1)) = 1 です。
0 + 2 + 1 + 0 + 1 = 4 であるため、4 を出力します。

入力例 2

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

出力例 2

14
16
10
16
14
16
8

Score : 600 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i.

Let d(x,y) denote the distance between vertex x and y in this tree. Here, the distance between vertex x and y is the number of edges on the shortest path from vertex x to y.

Answer Q queries in order. The i-th query is as follows.

  • You are given integers L_i and R_i. Find \displaystyle\sum_{j = 1}^{N} \min(d(j, L_i), d(j, R_i)).

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq A_i, B_i, L_i, R_i \leq N
  • The given graph is a tree.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
Q
L_1 R_1
\vdots
L_Q R_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

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

Sample Output 1

4
6
3

Let us explain the first query.
Since d(1, 4) = 2 and d(1, 1) = 0, we have \min(d(1, 4), d(1, 1)) = 0.
Since d(2, 4) = 2 and d(2, 1) = 2, we have \min(d(2, 4), d(2, 1)) = 2.
Since d(3, 4) = 1 and d(3, 1) = 3, we have \min(d(3, 4), d(3, 1)) = 1.
Since d(4, 4) = 0 and d(4, 1) = 2, we have \min(d(4, 4), d(4, 1)) = 0.
Since d(5, 4) = 1 and d(5, 1) = 1, we have \min(d(5, 4), d(5, 1)) = 1.
0 + 2 + 1 + 0 + 1 = 4, so you should print 4.

Sample Input 2

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

Sample Output 2

14
16
10
16
14
16
8