AT_abc438_f.[ABC438F] Sum of Mex

给你一棵有 $N$ 个顶点的树 $T$ 。顶点编号从 $0$ 到 $N-1$ ，第 $i$ 条边 $(1\le i\le N-1)$ 双向连接顶点 $u_i$ 和 $v_i$ 。(请注意，顶点编号以 $0$ 为索引，边编号以 $1$ 为索引）。

对于一对整数 $(i,j)$ 其中的 $0 \leq i,j < N$ ，定义 $f(i,j)$ 如下：

• 在树 $T$ 中，从顶点 $i$ 到顶点 $j$ 的路径中未包含的顶点中编号最小的顶点的顶点编号。
  • 这里，如果从顶点 $i$ 到顶点 $j$ 的路径包含了从顶点 $0$ 到顶点 $N-1$ 的所有顶点，则 $f(i,j)=N$ 。

请注意，树 $T$ 中从顶点 $i$ 到顶点 $j$ 的路径包括顶点 $i$ 和 $j$ 。

求 $\displaystyle \sum_{0\le i \le j < N} f(i,j)$ 的值。

输入内容由标准输入法提供，格式如下

$N\\$
$u_1$ $v_1\\$
$u_2$ $v_2\\$
$\vdots\\$
$u_{N-1}$ $v_{N-1}$

输出 $\displaystyle \sum_{0\le i \le j < N} f(i,j)$ 的值。

数据范围

• $2\le N\le 2\times 10^5$。
• $0\le u_i < v_i < N$。
• 输入的图形是一棵树。
• 所有输入值均为整数。

样例解释

样例 1 解释

我们得到 $f(0,0)=1,f(0,1)=2,f(1,1)=0$ 。因此，输出 $1+2+0=3$ 。