Heaps

题意翻译

给定一棵以 $1$ 为根的树,定义$dp_k(u)$表示在 $u$ 的子树内存在的深度最大的满 $k$ 叉树的深度,求$\sum_{u=1}^n∑_{k=1}^ndp_k(u)$。   以某个点 $x$ 为根存在一棵深度 $m$ 的满 $k$ 叉树是指,它满足下面任意一条: - $m=1$。 - 当 $m\neq1$ 时,$x$ 存在 $k$ 个子节点,分别以它们为根存在一棵深度为 $m−1$ 的满 $k$ 叉树。

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF955F/5de2414b533cccf22014f0b7eca5e58cbc6e8f9c.png).

输入输出格式

输入格式


The first line contains an integer $ n $ denoting the size of the tree $ (2<=n<=3·10^{5}) $ . 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.

输出格式


Output the answer to the task.

输入输出样例

输入样例 #1

4
1 3
2 3
4 3

输出样例 #1

21

输入样例 #2

4
1 2
2 3
3 4

输出样例 #2

22

说明

Consider sample case one. For $ k>=3 $ all $ dp_{k} $ will be equal to $ 1 $ . For $ k=2 $ $ dp_{k} $ is $ 2 $ if ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF955F/295fea3eafde0a7829eafa0db84ff6ad03162c9f.png) 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 $ .