Intervals on Tree

AtCoder

IDabc173_f

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

3
1 3
2 3

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$.

Input #2

2
1 2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Intervals on Tree",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc173_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\nFor integers $L, R$ ($1 \\leq L \\leq R \\leq N...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments