题意

题目链接。

给出一颗树，走到叶子节点后可以回到它的第 $k$ 祖先，求最多可以访问多少叶子节点。

解析

定义 $f_{i}$ 为从 $i$ 节点开始走，最后走回到 $i$ 节点的贡献，$g_i$ 为从 $i$ 节点开始走，最后不用回到 $i$ 节点的最大贡献。

先预处理出从每个点开始走可以回到的最高点，对于叶子节点，初始先将其贡献打到其第 $k$ 个祖先上，这部分代码如下：

inline void dfs(int u,int F){
    fa[u][0]=F;dep[u]=dep[F]+1;
    for(int i=1;i<=20;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    bool fl=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;//因为连边的时候仅仅从父亲向儿子连边了，所以这里未判返祖边。
        dfs(v,u);fl=0;
        if(!jp[u]||dep[jp[v]]<dep[jp[u]]) jp[u]=jp[v];//继承儿子可以跳到的最高点
    }
    if(fl){
        int x=u;
        for(int i=0;i<=20;i++){
            if(k&(1<<i)) x=fa[x][i];
        }//往上跳能跳到的最高点
        jp[u]=x;siz[x]++;//siz 即为贡献
    }
}

然后考虑对于一个点 $u$，对于其任意一个儿子 $v$，如果走到儿子能跳回到 $u$ 或 $u$ 的祖先，直接将 $f_u$ 加上 $f_v$ 即可。

接下来考虑转移 $g_u$，发现 $g_u$ 显然可以直接加上 $f_u$，然后其相当于要往某一个儿子走，最终不走回来。考虑每一个儿子的剩余价值，对于能跳回到 $u$ 或 $u$ 的祖先的儿子，其剩余价值为 $g_v-f_v$，对于其他儿子，其剩余价值就为 $g_v$，从所有儿子的剩余价值中取一个最大值加上即可。这部分代码如下：

inline void dfs2(int u){
    f[u]=siz[u];//初始打上的贡献先加上来
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        dfs2(v);
        if(dep[jp[v]]<=dep[u]) f[u]+=f[v];//能走回来的
    }
    g[u]=f[u];
    int maxx=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(dep[jp[v]]<=dep[u]) maxx=max(maxx,g[v]-f[v]);
        else maxx=max(maxx,g[v]);//找出剩余价值最高的那个
    }
    g[u]+=maxx;
}

时间复杂度为 $O(n\log k)$，有趣且不难。

核心代码已给出，连边后依次进行两个 dfs 再输出 $g_1$ 即可。