问题陈述
有一棵树 N 顶点,其顶点已编号 1, \dots, N 和边已编号 1, \dots, N-1。 边缘 i \, (1 \leq i \leq N - 1) 连接顶点 U_i 和 V_i.
求所有整数对的以下值的总和 (l, r) 这样 1 \leq l \leq r \leq N - 1:
- 从顶点可到达的顶点数 1 使用零个或多个边缘编号 l 和 r,包括在内。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq N - 1)
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
U_1 V_1
\vdots
U_{N - 1} V_{N - 1}
输出
打印答案。
示例输入 1
5 2 3 1 2 2 4 3 5
示例输出 1
24
例如,如果 (l, r) = (2, 4),可以从顶点得到 1 到顶点 1, 2,和 4;如果 (l, r) = (3, 3),可以从顶点得到 1 到顶点 1.
示例输入 2
2 1 2
示例输出 2
2
示例输入 3
7 1 2 2 7 4 6 3 6 4 5 1 5
示例输出 3
49