题目描述

江桥定义一棵树的其中一棵子树$^\texttt{[1]}$的权值为：将子树的所有节点编号从小到大排序后，形成数组的不动点$^\texttt{[2]}$数量。

现在江桥拿到了一棵有 $n$ 个节点，以 $n$ 为根的树，他想知道这棵树的所有子树的权值之和，请你帮帮他。

【名词解释】

$\hspace{15pt}$子树$^\texttt{[1]}$：树中某节点删掉与父亲相连的边后，该节点所在的子图。

$\hspace{15pt}$不动点$^\texttt{[2]}$：定义整数 $i\left(1\leqq i \leqq m \right)$ 是长度为 $m$ 的数组 $\{a_1,a_2,\dots,a_m\}$ 的一个不动点，当且仅当满足 $a_i = i$。

建议使用较快的读入方式。

输入格式

第一行输入一个整数 $n$，代表树的节点数量。 此后 $n - 1$ 行，第 $i$ 行输入两个整数 $u_i,v_i$，表示第 $i$ 条树边连接节点 $u_i$​ 和 $v_i$​。

输出格式

输出一个整数，代表子树权值之和。

4
3 4
2 4
1 2

7

4
1 3
2 3
4 3

8

4
1 4
2 4
4 3

5

样例解释

无

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 2 \times 10^{5},1 \leq u_i,v_i \leq n$，输入保证构成一棵树。