题解 CF1009F 【Dominant Indices】

首先这个题可以想到是一个DP。状态设计： $f_{u,dep}$ 表示 u 的子树中与 u 距离为 dep 的点的个数。
转移方程如下:

f_{u,dep}=\sum_{v \in son_u} f_{v,dep-1}

然而如果直接暴力转移的话显然会 T 飞或者 M 飞，，所以我们需要一点点的优化。

引入一个概念：长链剖分

我们可以找到一个结点 u 的子树中，到这个节点距离最大的叶子节点。将两点之间的距离计为 $dep_u$ 。那么对于一个节点 u，我们把他的所有孩子中 dep 值最大的称作这个节点的 长儿子。

从一个节点开始，每次走向他的长儿子，一直走到叶子节点为止，经过的路径就是一条长链。显然，一整棵树会被分成若干条长链，并且每个节点都在恰好一条长链上，每条边要么在长链上，要么把一条长链的顶端连向另一条长链。

代码如下：


int dep[1000005],son[1000005];
void dfs1(int u,int fa)
{
    for (int e=head[u];e;e=nex[e]) // 链式前向星
    {
        int v=tail[e];
        if (v==fa) continue;
        dfs1(v,u);
        if (dep[v]>dep[son[u]]) son[u]=v; // 寻找长儿子
    }
    dep[u]=dep[son[u]]+1; // 统计 u 的 dep
}

那么这个东西和 DP 又有什么关系呢？

我们可以采用一个优化策略：对于一个节点 u，我们先对它的长儿子做DP，但这里可以使用一些技巧，让长儿子把 dp 出来的东西直接存到 $f_u$ 里面去（当然观察 dp 式可以发现这边需要错一位），然后再把其他儿子 dp 出来的东西与 $f_u$ 暴力合并。

这里详细地说一说到底怎么样实现这个优化（貌似其他题解写得都很简略啊……窝看了半天都看不懂，可能是我太菜了）

首先，我们抛弃传统 DP 的预先为每个节点都申请一片空间的写法（空间开销过大），而是在 DP 的过程中，动态的为节点申请（DP数组的）内存，所以这里我们要采用指针的写法。

然后，我们只对每一个长链的顶端节点申请内存，而对于一条长链上的所有节点，我们让他们可以公用一片空间。具体地说，假设对节点 u 申请了内存之后，设 v 是 u 的长儿子，我们就把 $f_u$ 数组的起点（的指针）加一当作 $f_v$ 数组的起点（的指针，下同），以此类推。这也就是上面说的“让长儿子把 dp 出来的东西直接存到 $f_u$ 里面去”。当然，申请的内存要能装下一条长链。

那么显而易见的，使用了这个优化之后可以把时间和空间都减到 $O(n)$ 级别的，因为每个节点都只会在它所在的长链顶端被统计（或者说是被暴力合并）一次。

这部分优化的代码长成这个样子：

void dfs2(int u,int fa)
{
    f[u][0]=1; // 先算上自己
    if (son[u])
    {
        f[son[u]]=f[u]+1; // 共享内存，这样一步之后，f[son[u]][dep]会被自动保存到f[u][dep-1]
        dfs2(son[u],u);
    }
    for (int e=head[u];e;e=nex[e])
    {
        int v=tail[e];
        if (v==son[u] || v==fa) continue;
        f[v]=now;now+=dep[v]; // 为 v 节点申请内存，大小等于以 v 为顶端的长链的长度
        dfs2(v,u);
        for (int i=1;i<=dep[v];i++)
        {
            f[u][i]+=f[v][i-1]; //暴力合并
        }
    }
}

当然，在 dp 开始前要先为以树根为顶端的长链申请内存。

然而，光有 dp 数组还没用，我们还要统计答案。

我们可以先令 u 节点的答案为它的长儿子的答案加一。然后在暴力合并的过程当中每次检查当前的 dep 是否优于 $ans_u$ （ $ans_u$ 就是题目要求的东西），如果是的话那就更新答案。

最后如果发现 $f_{u,ans_u}=1$ ，即 u 的子树为一条链，无论在哪个深度下都只有一个点的话，那么就把当前节点的答案 $ans_u$ 设为 0 ，这个应该很好理解。

最后放上完整的代码：

#include <bits/stdc++.h>
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define in inline
#define re register
using namespace std;
typedef long long ll;
typedef double db;
in int read()
{
    int ans=0,f=1;char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48);
    return ans*f;
}
in int cmin(int &a,int b) {return a=min(a,b);}
in int cmax(int &a,int b) {return a=max(a,b);}
int n;
int buf[1000005];
int *f[1000005],*g[1000005],*now=buf;
int nex[2000005],head[1000005],tail[2000005],tot;
int ans[1000005];
void addedge(int u,int v)
{
    nex[++tot]=head[u];
    head[u]=tot;
    tail[tot]=v;
}
int dep[1000005],son[1000005];
void dfs1(int u,int fa) // 长链剖分
{
    for (int e=head[u];e;e=nex[e])
    {
        int v=tail[e];
        if (v==fa) continue;
        dfs1(v,u);
        if (dep[v]>dep[son[u]]) son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int fa) //做dp
{
    f[u][0]=1;
    if (son[u])
    {
        f[son[u]]=f[u]+1; // 共享内存
        dfs2(son[u],u);
        ans[u]=ans[son[u]]+1; //从长孩子节点继承答案
    }
    for (int e=head[u];e;e=nex[e])
    {
        int v=tail[e];
        if (v==son[u] || v==fa) continue;
        f[v]=now;now+=dep[v]; // 分配内存
        dfs2(v,u);
        for (int i=1;i<=dep[v];i++)
        {
            f[u][i]+=f[v][i-1]; //暴力合并
            if (f[u][i]>f[u][ans[u]] || (f[u][i]==f[u][ans[u]] && i<ans[u])) ans[u]=i; //更新答案
        }
    }
    if (f[u][ans[u]]==1) ans[u]=0;
}
int main()
{
    n=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,0); // 长链剖分
    f[1]=now;now+=dep[1]; // 为根节点的答案分配内存
    dfs2(1,0);
    for (int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}

完结撒花*★,°*:.☆(￣▽￣)/$:*.°★* 。！

Thomasguo666的小屋

题解 CF1009F 【Dominant Indices】

题解 P2278 【[HNOI2003]操作系统】