题解 CF1009F 【Dominant Indices】
Thomasguo666
2020-04-08 21:25:20
更好的阅读体验：https://thomasguo666.github.io/post/solution-cf1009f/
---
首先这个题可以想到是一个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 值最大的称作这个节点的 **长儿子**。
从一个节点开始，每次走向他的长儿子，一直走到叶子节点为止，经过的路径就是一条**长链**。显然，一整棵树会被分成若干条长链，并且每个节点都在恰好一条长链上，每条边要么在长链上，要么把一条长链的顶端连向另一条长链。
代码如下：
```cpp
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)$ 级别的，因为每个节点都只会在它所在的长链顶端被统计（或者说是被暴力合并）一次。
这部分优化的代码长成这个样子：
```cpp
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 ，这个应该很好理解。
最后放上完整的代码：
```cpp
#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;
}
```
完结撒花\*★,°\*:.☆(￣▽￣)/$:\*.°★\* 。！