CF955F Heaps

解法比较多，但是比较简单，有点套路。

解法一：DP 换维

首先考虑暴力求出 $dp_k(u)$，容易得到暴力的状态转移方程：$dp_k(u)=\text{kthmax}_v dp_k(v) +1$。我们容易以下两点：

$dp_k(u)\le \log_k n$。
$dp_k(u)\ge dp_{k+1}(u)$。

根据这两点，我们容易想到换维，设计 $f_i(u)$ 表示子树 $u$ 中深度为 $i$ 的最多是 $f_i(u)$ 叉树。状态转移方程与上面几乎一样，最后对子树取 $\max$ 即可。时间复杂度为 $\mathcal O(n\log n)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
using ll=long long;
const int N=3e5+10,K=18;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n;
int tot,head[N],ver[N<<1],ne[N<<1];
int f[N][K+2],d[N];
vector<int>res;
inline bool cmp(const int &x,const int &y){return x>y;}
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void dfs(int x,int fa)
{
    f[x][1]=n;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        dfs(y,x);
        d[x]=max(d[x],d[y]);
    }
    d[x]++;
    for(int k=1;k<=K;k++)
    {
        res.clear();
        for(int i=head[x];i;i=ne[i])
        {
            int y=ver[i];
            if(y==fa)continue;
            res.push_back(f[y][k-1]);
        }
        sort(res.begin(),res.end(),cmp);
        int si=res.size();
        for(int i=0;i<si;i++)
            f[x][k]=max(f[x][k],min(res[i],i+1));
    }
}
void get_max(int x,int fa)
{
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(y==fa)continue;
        get_max(y,x);
        for(int k=1;k<=K;k++)f[x][k]=max(f[x][k],f[y][k]);
    }
}
int main()
{
    read(n);
    for(int i=1,u,v;i<n;i++)read(u,v),add(u,v),add(v,u);
    dfs(1,0);
    get_max(1,0);
    ll ans=0;
    for(int i=1;i<=n;i++)ans+=d[i];
    for(int i=1;i<=n;i++)
        for(int k=1;k<=K;k++)
            ans+=max(f[i][k]-1,0);
    printf("%lld\n",ans);
    return 0;
}

解法二：启发式合并或线段树合并

设 $f_k(u)$ 表示以 $u$ 根的 $k$ 叉树深度，注意到 $f(u)$ 状态数等于其儿子的个数 $|\text{son}(x)|$，状态数是 $\mathcal O(n)$ 的，容易线性求出。

考虑 $dp_k(u)=\max_{v\in \text{son}(u)}f_k(v)$，这一部分可以考虑启发式合并或者线段树合并解决，这样时间复杂度为 $\mathcal O(n\log n)$。

解法三：虚树

或者说，我们考虑对于 $k=1,2,3,\cdots,n$ 求出 $\sum_udp_k(u)$。我们发现 $f_k(u)$ 有值即 $|\text{son}(x)|\ge k$ 时，向上传递的 $\max_{v\in \text{son}(u)}f_k(v)$ 才会发生改变。于是我们枚举 $k$，考虑对 $|\text{son}(x)|\ge k$ 的节点建虚树，再利用深度 $dep_u$ 计算中间的贡献。实现的足够优秀可以做到线性。

解法一：DP 换维

解法二：启发式合并 或 线段树合并

解法三：虚树

解法二：启发式合并或线段树合并