V - Connectivity 2 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 6 点

問題文

頂点に 1 から N の番号が付いた N 頂点の木があります。 i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。

整数の区間 [a,b] が good であるとは、頂点 a,a+1,\ldots,b からなる誘導部分グラフが 連結であることをいいます。

クエリを Q 個処理してください。i 番目のクエリでは整数 L_i,R_i が与えられるので、 次の条件をともに満たす整数の組 (a,b) の個数を求めてください。

  • L_i \leq a \leq b \leq R_i
  • 区間 [a,b] は good である

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i \lt v_i \leq N
  • 与えられるグラフは木
  • 1 \leq L_i \leq R_i \leq N
  • 入力される数値はすべて整数

入力

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

N Q
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

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

入力例 1

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

出力例 1

9
7
3
1

good な区間は以下の 9 個です。

[1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5]

入力例 2

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

出力例 2

17
3
9

Score: 6 points

Problem Statement

There is a tree with N vertices numbered from 1 to N. Edge i connects vertices u_i and v_i.

An integer interval [a,b] is good if the subgraph induced by vertices a,a+1,\ldots,b is connected.

Process Q queries. In the i-th query, you are given integers L_i,R_i. Find the number of pairs of integers (a,b) satisfying both of the following conditions:

  • L_i \leq a \leq b \leq R_i
  • The interval [a,b] is good.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq u_i \lt v_i \leq N
  • The given graph is a tree.
  • 1 \leq L_i \leq R_i \leq N
  • All numerical values in the input are integers.

Input

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

N Q
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
L_1 R_1
L_2 R_2
\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 4
1 4
2 4
3 5
4 5
1 5
2 5
1 3
4 4

Sample Output 1

9
7
3
1

The following 9 intervals are good:

[1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5]

Sample Input 2

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

Sample Output 2

17
3
9