\(\tt CF955F\)，\(\tt^\ast2600\)。
首先要知道：设 \(deg_u\) 为 \(u\) 的儿子个数，有 \(\sum deg_u=O(n)\)。
我们考虑求出 \(dp_k(u)\)，然后一个一个加。
但是这个不太好直接求，所以可以求出一个弱化一点的东西：\(f_k(u)\) 代表 \(u\) 子树内 以 \(u\) 为根 的 \(k\) 叉树最大深度。
容易发现 \(f_k(u)\) 分成两类，一类 \(\gt1\)，一类 \(=1\)。容易发现后者居多，而前者只有 \(\sum deg_u=O(n)\) 种。
我们希望让复杂度尽量优秀，于是考虑 \(O(n)\) 的时间里求出 \(f_{k}(u)\) 的所有非 \(1\) 状态。
我们考虑树形 \(\tt DP\) 来求这个东西，设 \(S_{u,k}=\{f_{v,k}\}\)，其中 \(v\) 是 \(u\) 的儿子，那么有 \(f_{u,k}=\mathtt{kth}(S_{u,k},k)+1\)，其中 \(\tt kth\) 是取 \(k\) 大的意思。
原因很显然，如果第 \(k\) 大为 \(x\)，说明至少有 \(k\) 个 \(v\) 使得 \(f_{v,k}\ge x\)，那么以这 \(k\) 个儿子各自建 \(k\) 叉树，\(u\) 连向着 \(k\) 个儿子，新 \(k\) 叉树深度一定 \(\ge x+1\)。
\(\tt kth\) 就是 \(\texttt{std::nth\_element}\)。
那我们怎么通过这个 \(f\) 推到复杂的 \(dp\) 呢？其实 \(dp\) 就是 \(f\) 的子树最大值。但是 \(dp\) 不能直接暴力累加，因为它的状态数不是 \(O(n)\) 的。
我们分开每个 \(k=1,\cdots,n\) 来处理 \(\sum dp_k(u)\)，对于某个 \(k\)，我们把 \(deg_u\le k\) 的 \(u\) 建成一棵虚树（复杂度 \(\sum deg_u\)）。
我们考虑虚树上一条边 \(fa\to u\)，并且 \(dp_k(u)=x\)。这时候对于 \(p\in\{fa,\cdots,u\}\) 这条链除去 \(fa\)，\(dp_k(p)=x\)。所以 \(u\) 的贡献是 (dep[u]-dep[fa])*dp[u][k]。
那就是一个简单的虚树 \(\tt DP\) 了。
求 \(f\) 和虚树 \(\tt DP\) 都可以很简单的做到线性。（我的实现）做不到线性的原因是我不想写 \(O(n)-O(1)\) 的 \(\tt LCA\)（建虚树），最后就是 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n,dep[N],dfn[N],deg[N],tot;
vector<int> G[N],T[N],dp[N],tmp[N],P,Q;
long long cnt;
int d,ft[20][N],stk[N];
void dfs(int u,int fa){
dep[u] = dep[ft[0][u] = fa] + 1; dfn[u] = ++tot;
dp[u].resize(1 + (deg[u] = G[u].size() - (u != 1)));
if(deg[u]) P.push_back(u);
for(int i = 1;i < 20;++i) ft[i][u] = ft[i - 1][ft[i - 1][u]];
for(int v : G[u]) if(v != fa) dfs(v,u);
for(int v : G[u]) if(v != fa)
for(int j = 1;j <= min(deg[u],deg[v]);++j) tmp[j].push_back(dp[v][j]);
for(int i = 1;i <= deg[u];++i){
if(tmp[i].size() < i){ dp[u][i] = 2; tmp[i].clear(); continue; }
auto p = begin(tmp[i]) + (i - 1);
nth_element(begin(tmp[i]),p,end(tmp[i]),greater<int>());
dp[u][i] = *p + 1; tmp[i].clear();
}
}
int lca(int u,int v){
if(dep[u] < dep[v]) swap(u,v);
for(int i = 19;~i;--i) if(dep[v] <= dep[u] - (1 << i)) u = ft[i][u];
if(u == v) return u;
for(int i = 19;~i;--i) if(ft[i][u] != ft[i][v]) u = ft[i][u],v = ft[i][v];
return ft[0][u];
}
int ans(int u,int ft){
int R = deg[u] < d ? 1 : dp[u][d];
for(int v : T[u]) R = max(R,ans(v,u));
T[u].clear();
return cnt += 1LL * (dep[u] - dep[ft]) * (R - 1),R;
}
int main(){
scanf("%d",&n);
for(int i = 1,u,v;i < n;++i){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(d = 1;d <= n;++d){
int tp = 0;
for(int x : P){
if(!tp){ stk[++tp] = x; continue; }
int z = lca(stk[tp],x);
while(dep[z] < dep[stk[tp - 1]])
T[stk[tp - 1]].push_back(stk[tp]),--tp;
if(z != stk[tp]){
T[z].push_back(stk[tp]);
stk[tp - 1] == z ? --tp : stk[tp] = z;
}
stk[++tp] = x;
}
while(--tp) T[stk[tp]].push_back(stk[tp + 1]);
ans(1,0); swap(P,Q); P.clear();
for(int x : Q) if(deg[x] != d || x == 1) P.push_back(x);
}
printf("%lld\n",cnt + (1LL * n * n));
return 0;
}