/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点 N-1 辺から成る木があり、頂点には 1, 2,\cdots, N の番号が、辺には 1, 2, \cdots, N-1 の番号がついています。辺 i は頂点 u_i, v_i を繋いでいます。
整数 1 \leq L \leq R \leq N に対して関数 f(L, R) を次のように定義します。
- S を番号が L 以上 R 以下の頂点から成る集合とする。頂点集合 S と、両端が S に属する辺のみから成るような部分グラフの連結成分の個数を f(L, R) で表す。
\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R) を計算してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- 与えられるグラフは木である
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
出力
\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R) を出力せよ。
入力例 1
3 1 3 2 3
出力例 1
7
考えられる L, R の組み合わせは以下の 6 通りがあります。
- L = 1, R = 1 のとき、S = \{1\} であり、連結成分の個数は 1 です。
- L = 1, R = 2 のとき、S = \{1, 2\} であり、連結成分の個数は 2 です。
- L = 1, R = 3 のとき、S = \{1, 2, 3\} であり、辺 1, 2 は両端が S に含まれるので、連結成分の個数は 1 です。
- L = 2, R = 2 のとき、S = \{2\} であり、連結成分の個数は 1 です。
- L = 2, R = 3 のとき、S = \{2, 3\} であり、辺 2 は両端が S に含まれるので、連結成分の個数は 1 です。
- L = 3, R = 3 のとき、S = \{3\} であり、連結成分の個数は 1 です。
これらの和は 7 です。
入力例 2
2 1 2
出力例 2
3
入力例 3
10 5 3 5 7 8 9 1 9 9 10 8 4 7 4 6 10 7 2
出力例 3
113
Score : 600 points
Problem Statement
We have a tree with N vertices and N-1 edges, respectively numbered 1, 2,\cdots, N and 1, 2, \cdots, N-1. Edge i connects Vertex u_i and v_i.
For integers L, R (1 \leq L \leq R \leq N), let us define a function f(L, R) as follows:
- Let S be the set of the vertices numbered L through R. f(L, R) represents the number of connected components in the subgraph formed only from the vertex set S and the edges whose endpoints both belong to S.
Compute \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N
- The given graph is a tree.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
Output
Print \sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R).
Sample Input 1
3 1 3 2 3
Sample Output 1
7
We have six possible pairs (L, R) as follows:
- For L = 1, R = 1, S = \{1\} and we have 1 connected component.
- For L = 1, R = 2, S = \{1, 2\} and we have 2 connected components.
- For L = 1, R = 3, S = \{1, 2, 3\} and we have 1 connected component, since S contains both endpoints of each of the edges 1, 2.
- For L = 2, R = 2, S = \{2\} and we have 1 connected component.
- For L = 2, R = 3, S = \{2, 3\} and we have 1 connected component, since S contains both endpoints of Edge 2.
- For L = 3, R = 3, S = \{3\} and we have 1 connected component.
The sum of these is 7.
Sample Input 2
2 1 2
Sample Output 2
3
Sample Input 3
10 5 3 5 7 8 9 1 9 9 10 8 4 7 4 6 10 7 2
Sample Output 3
113