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 $ .