CF955F.Heaps

You're given a tree with n vertices rooted at 1.

We say that there's a k-ary heap of depth m located at u if the following holds:

• For m = 1 u itself is a k-ary heap of depth 1.
• For m > 1 vertex u is a k-ary heap of depth m if at least k of its children are k-ary heaps of depth at least m - 1.

Denote dp__k(u) as maximum depth of k-ary heap in the subtree of u (including u). Your goal is to compute .

给你一棵以 1 为根、包含 $ n $ 个顶点的树。

我们称在顶点 $ u $ 处存在一个深度为 $ m $ 的 $ k $-叉堆，当且仅当满足以下条件：

• 当 $ m = 1 $ 时，$ u $ 本身即为一个深度为 1 的 $ k $-叉堆；
• 当 $ m > 1 $ 时，顶点 $ u $ 是一个深度为 $ m $ 的 $ k $-叉堆，当且仅当其至少有 $ k $ 个子节点是深度至少为 $ m - 1 $ 的 $ k $-叉堆。

记 $ dp_k(u) $ 为以 $ u $ 为根的子树（含 $ u $）中所能构成的 $ k $-叉堆的最大深度。你的目标是计算

The first line contains an integer n denoting the size of the tree (2 ≤ n ≤ 3·105).

The next n - 1 lines contain two integers u, v each, describing vertices connected by i-th edge.

It's guaranteed that the given configuration forms a tree.

第一行包含一个整数 $n$，表示树的大小（$2 \leq n \leq 3 \cdot 10^5$）。

接下来的 $n-1$ 行每行包含两个整数 $u$、$v$，描述第 $i$ 条边所连接的两个顶点。

保证给定的结构构成一棵树。

Output the answer to the task.

输出任务的答案。

Consider sample case one.

For k ≥ 3 all dp__k will be equal to 1.

For k = 2 dp__k is 2 if and 1 otherwise.

For k = 1 dp__k values are (3, 1, 2, 1) respectively.

To sum up, 4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21.

考虑样例一。

当 $k \geq 3$ 时，所有 $dp_k$ 均等于 1。

当 $k = 2$ 时，若 ，则 $dp_k = 2$；否则 $dp_k = 1$。

当 $k = 1$ 时，对应的 $dp_k$ 值依次为 $(3, 1, 2, 1)$。

综上，$4·1 + 4·1 + 2·2 + 2·1 + 3 + 1 + 2 + 1 = 21$。