AT_abc438_f [ABC438F] Sum of Mex

You are given a tree $ T $ with $ N $ vertices. The vertices are numbered from $ 0 $ to $ N-1 $ , and the $ i $ -th edge $ (1\le i\le N-1) $ bidirectionally connects vertices $ u_i $ and $ v_i $ . (Note that vertex numbers are 0-indexed and edge numbers are 1-indexed.) For a pair of integers $ (i,j) $ where $ 0 \leq i,j < N $ , define $ f(i,j) $ as follows: - The vertex number of the vertex with the smallest number among the vertices **not included** in the path from vertex $ i $ to vertex $ j $ in tree $ T $ . - Here, if the path from vertex $ i $ to vertex $ j $ includes all vertices from vertex $ 0 $ to vertex $ N-1 $ , let $ f(i,j)=N $ . Note that the path from vertex $ i $ to vertex $ j $ in tree $ T $ includes vertices $ i $ and $ j $ . Find the value of $ \displaystyle \sum_{0\le i \le j < N} f(i,j) $ .

The input is given from Standard Input in the following format: > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

Output the value of $ \displaystyle \sum_{0\le i \le j < N} f(i,j) $ .

### Sample Explanation 1 We have $ f(0,0)=1,f(0,1)=2,f(1,1)=0 $ . Thus, output $ 1+2+0=3 $ . ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ 0\le u_i < v_i < N $ - The graph given in the input is a tree. - All input values are integers.