题意
给定一棵以 (1) 号点为根的树。若满足以下条件，则认为节点 (p) 处有一个 (k) 叉高度为 (m) 的堆:
- 若 (m = 1) ，则 (p) 本身就是一个 (k) 叉高度为 (1) 的堆。
- 若 (m > 1) ，则 (p) 需要有至少 (k) 个儿子满足在儿子处有一个 (k) 叉高度为 (m − 1) 的堆。
令 (dp[p][k]) 表示在 (p) 点 (k) 叉堆的最大高度，令 (g[p][k]) 为 (p) 子树内最大的 (dp[v][k]) 求 (displaystyle sum_{i=1}^{n} sum_{j=1}^{n} g[i][j]) 。
(n le 3 ∗ 10^5)
题解
如果固定一个 (k) ，然后直接暴力做 (dp) ，每次是 (O(n ^ 2)) 的。
但显然是没必要这么暴力的，因为我们发现对于任意 (k > 1) ，都存在 (dp[p][k] le log_{k} n) 。
所以我们可以考虑做对于这个 (dp) 值的 (dp) ，具体来说令 (f[p][x]) 为满足 (dp[p][k] le x) 的最大的 (k) 。
不难发现这样总状态是 (O(n log n)) 的，接下来我们只需要考虑如何转移这个 (dp) 了。
考虑枚举一个点 (p) ，然后枚举它当前的层数 (x le 20) ，然后考虑从它所有儿子的 (x-1) 的状态转移过来。
这个点的 (f) 取值显然不会超过儿子总数，然后考虑从大到小枚举 (f) 的取值 (k) 然后判断 (f[v][x - 1]) （ (v) 是 (u) 的一个儿子）中第 (k) 大的取值是否 (ge k) ，如果可以则能取这个值。
这是因为它有 (k) 个儿子都满足至少具有 (k) 叉树的条件，那么这个点也能满足 (k) 叉树的条件。
然后最后记得要考虑 (k=1) 的情况（直接找向下最长链），然后答案就是 (sum_{i} (dep_i +sum_{j} (f[i][j] - 1))) 。
复杂度就是 (O(n log n ) imes O(log n) = O(n log^2 n)) 的（因为有排序）。
总结
如果对于 (dp) 状态很多，但是取值很小的题，可以考虑对于 (dp) 值进行转移，常常状态就可以压到很少。
代码
其实很好写qwq
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define pb push_back
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("F.in", "r", stdin);
freopen ("F.out", "w", stdout);
#endif
}
const int N = 3e5 + 1e3, Lim = 20;
vector<int> G[N];
int n, f[N][Lim + 1], g[N], len;
void Dp(int u, int fa) {
for (int v : G[u]) if (v != fa) Dp(v, u);
f[u][1] = n;
For (i, 2, Lim) {
len = 0; for (int v : G[u]) if (v != fa) g[++ len] = f[v][i - 1];
sort(g + 1, g + len + 1, greater<int>());
Fordown (k, len, 1) if (g[k] >= k) { f[u][i] = k; break; }
}
}
int dep[N];
void Dfs(int u, int fa) {
dep[u] = 1;
for (int v : G[u]) if (v != fa) {
Dfs(v, u);
chkmax(dep[u], dep[v] + 1);
For (i, 1, Lim)
chkmax(f[u][i], f[v][i]);
}
}
long long ans = 0;
int main () {
File();
n = read();
For (i, 1, n - 1) {
int u = read(), v = read();
G[u].pb(v); G[v].pb(u);
}
Dp(1, 0); Dfs(1, 0);
For (i, 1, n) {
ans += dep[i];
For (j, 1, Lim)
if (f[i][j]) ans += f[i][j] - 1;
}
printf ("%lld
", ans);
return 0;
}