CF955F Heaps

给定一棵以 $1$ 为根的 $n$ 个结点的树。 我们称在结点 $u$ 处存在一个深度为 $m$ 的 $k$ 叉堆，当且仅当满足以下条件： - 当 $m=1$ 时，$u$ 本身就是一个深度为 $1$ 的 $k$ 叉堆。 - 当 $m>1$ 时，若 $u$ 的至少 $k$ 个子节点分别是深度至少为 $m-1$ 的 $k$ 叉堆，则 $u$ 是一个深度为 $m$ 的 $k$ 叉堆。 记 $dp_{k}(u)$ 表示以 $u$ 为根的子树中（包括 $u$ 本身）最大的 $k$ 叉堆深度。你的任务是计算下式的值： $$ \sum_{u=1}^{n} \sum_{k=1}^{n} dp_{k}(u) $$

第一行包含一个整数 $n$，表示树的结点数，$2 \leq n \leq 3 \cdot 10^{5}$。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示第 $i$ 条边连接的两个结点。 保证给定的结构是一棵树。

输出题目要求的答案。

以样例一为例： 对于 $k \geq 3$，所有 $dp_{k}$ 都等于 $1$。 对于 $k=2$，当结点的度数大于等于 $2$ 时，$dp_{k}$ 为 $2$，否则为 $1$。 对于 $k=1$，$dp_{k}$ 分别为 $(3,1,2,1)$。 综上，$4 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 1 + 3 + 1 + 2 + 1 = 21$。 由 ChatGPT 4.1 翻译