{"raw_statement":[{"iden":"problem statement","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$), let us define a function $f(L, R)$ as follows:\n\n*   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$.\n\nCompute $\\sum_{L=1}^{N} \\sum_{R=L}^{N} f(L, R)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq u_i, v_i \\leq N$\n*   The given graph is a tree.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$:$\n$u_{N-1}$ $v_{N-1}$"},{"iden":"sample input 1","content":"3\n1 3\n2 3"},{"iden":"sample output 1","content":"7\n\nWe have six possible pairs $(L, R)$ as follows:\n\n*   For $L = 1, R = 1$, $S = {1}$ and we have $1$ connected component.\n*   For $L = 1, R = 2$, $S = {1, 2}$ and we have $2$ connected components.\n*   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$.\n*   For $L = 2, R = 2$, $S = {2}$ and we have $1$ connected component.\n*   For $L = 2, R = 3$, $S = {2, 3}$ and we have $1$ connected component, since $S$ contains both endpoints of Edge $2$.\n*   For $L = 3, R = 3$, $S = {3}$ and we have $1$ connected component.\n\nThe sum of these is $7$."},{"iden":"sample input 2","content":"2\n1 2"},{"iden":"sample output 2","content":"3"},{"iden":"sample input 3","content":"10\n5 3\n5 7\n8 9\n1 9\n9 10\n8 4\n7 4\n6 10\n7 2"},{"iden":"sample output 3","content":"113"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}