给你一棵树,有 n 个顶点,根为 1。
如果满足以下条件,我们就说在 u 处存在一个深度为 m 的 k 元堆:
- 对于 m = 1 u 本身是深度为 1 的 k 元堆。
- 对于 m > 1 顶点 u 是深度为 m 的 k 元堆,如果其至少 k 个子堆是深度至少为 m - 1 的 k 元堆。
将 dpk(u) 表示为 u(包括 u)的子树中 k 元堆的最大深度。您的目标是计算 $$\sum_{k=1}^{n}\sum_{u=1}^{n}dp_k(u)$$。
输入
第一行包含一个整数n,表示树的大小(2 ≤ n ≤ 3·105)。
接下来的 n - 1 行各包含两个整数 u、v,描述由第 i 条边连接的顶点。
保证给定的配置形成一棵树。
输出
输出任务的答案。
示例
输入 #1
4 1 3 2 3 4 3
输出 #1
21
输入 #2
4 1 2 2 3 3 4
输出 #2
22
注意
考虑示例案例一。
对于 k ≥ 3,所有 dpk 将等于 1。
对于 k = 2,如果 $$u \in 1,3$$ 则 dpk 为 2,否则为 1。
对于 k = 1,dpk 值分别为 (3, 1, 2, 1)。
总而言之,4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21。