{"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$), 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)$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc173_f","tags":[],"sample_group":[["3\n1 3\n2 3","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$."],["2\n1 2","3"],["10\n5 3\n5 7\n8 9\n1 9\n9 10\n8 4\n7 4\n6 10\n7 2","113"]],"created_at":"2026-03-03 11:01:14"}}