← 返回题目列表

Codeforces · 955/F

F. 堆

中文机器翻译题面 查看原题

给你一棵树,有 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。