Boba Fett is flying around Cloud City looking for Han Solo so that he can cash in his sizable bounty. He is given a map of $$$n$$$ possible locations at which Han could be and Boba wants to set up some traps around these locations. There are $$$n-1$$$ routes between these locations labeled with $$$e_1, e_2, \dots, e_{n - 1}$$$. These routes form a tree, in which each vertex represents a location and each edge $$$(u, v)$$$ represents a route between locations $$$u$$$ and $$$v$$$.
Let $$$T$$$ be the tree that represents Boba's map. For $$$1 \leq l \leq r \leq n - 1$$$, let $$$T_{l,r}$$$ denote the subgraph of $$$T$$$ obtained from $$$T$$$ by removing all edges not in $$$\{e_l, e_{l+1}, \dots, e_r\}$$$ and all vertices not incident to any edge in $$$\{e_l, e_{l+1}, \dots, e_r\}$$$. Note that $$$T_{l,r}$$$ may not be a tree, but it must be a forest. An interval $$$[l,r]$$$ is called a trap if both of the following hold:
- $$$1 \leq l \leq r \leq n - 1$$$,
- $$$T_{l,r}$$$ is a tree.
In other words, it's a singular connected component and therefore allows Boba to trap his target in those locations. Boba wants your help in counting the total number of possible traps he could set.
For simplicity, we assume that the vertices of $$$T$$$ are numbered by $$$1, 2, \dots, n$$$. Consider the tree $$$T$$$ in Figure 1(a). Figure 1(b) shows $$$T_{2, 4}$$$, which contains the edges $$$\{e_2, e_3, e_4\}$$$ and the vertices incident to at least one of these edges. Figure 1(c) gives $$$T_{2, 6}$$$. In this example, $$$[2, 4]$$$ is a trap because $$$T_{2, 4}$$$ is a tree; $$$[2, 6]$$$ is not a trap, because $$$T_{2,6}$$$ has two connected components.
The first line of the input contains the integer $$$n$$$ $$$(2 \leq n \leq 1.5 \times 10^5)$$$ — the number of nodes in the tree $$$T$$$.
Each of the next $$$n - 1$$$ lines describes an edge of the tree:
The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$ — the two endpoints of the edge $$$e_i$$$.
It is guaranteed that the given edges form a tree of $$$n$$$ nodes.
Output one integer, indicating the number of possible traps. (Please note that the answer may not fit into a 32-bit integer. We advise using 64-bit integers.)
95 63 14 54 37 87 97 42 1
20
71 22 33 44 55 66 7
21
112 31 23 42 52 67 81 78 96 102 11
21
21 2
1
The first example is given in Figure 1. There are $$$19$$$ possible traps: $$$[1, 1]$$$, $$$[1, 4]$$$, $$$[1, 7]$$$, $$$[1, 8]$$$, $$$[2, 2]$$$, $$$[2, 4]$$$, $$$[2, 7]$$$, $$$[2, 8]$$$, $$$[3, 3]$$$, $$$[3, 4]$$$, $$$[3, 7]$$$, $$$[4, 4]$$$, $$$[4, 7]$$$, $$$[5, 5]$$$, $$$[5, 6]$$$, $$$[5, 7]$$$, $$$[6, 6]$$$, $$$[6, 7]$$$, $$$[7, 7]$$$, and $$$[8, 8]$$$.
The second example is a path of $$$6$$$ edges, in which the edges are labeled in increasing order from left to right. In this example, all $$$21$$$ intervals are possible traps.
