P4228 [清华集训2017] 榕树之心 做题记录

题目描述

一棵 $n$ 个结点的有根树，其中结点编号为 $1\sim n$，而 $1$ 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 $n$ 个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。求哪些结点可能是心在生长过程结束时停留的位置呢？多组数据，$n\le10^5$，数据组数 $T\le20$。时间限制 $\rm{3s}$，内存限制 $\rm{500MB}$

---

Part 1

考虑根节点 $1$ 的答案。我们发现如果心在节点 $u$ 那么我们拓展 $u$ 的两个子树 $v_1,v_2$。那么我们可以定义 $f_i$ 为如果心在 $i$ 时拓展其所有子树能够让心移动到的位置距 $i$ 的最小值。

$$\displaylines{\displaylines { \text{令}v=hson_u\\ f_i=\begin{cases} (siz_u-1)\bmod2&f_v+1\le siz_u-1-siz_v\\ f_v+1-(siz_u-siz_v-1)& \mathrm{otherwise} \end{cases}} }$$

由于只考虑了每个节点的子树，没考虑其他部分，所以通过该方法只能求出 $1$ 的答案。

---

Code

int son[N],son2[N],siz[N],f[N];
inline void dfs1(int u,int fa)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa) continue;
        dfs1(v,u);siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son2[u]=son[u],son[u]=v;
        else if(siz[v]>siz[son2[u]]) son2[u]=v;
    }
    f[u]=(f[son[u]]<=siz[u]-1-siz[son[u]])?((siz[u]-1)&1):(f[son[u]]-(siz[u]-1-siz[son[u]]));
    f[u]++;
}

---

Part 2

考虑将答案拓展到任意点上。我们先把心从 $1$ 挪到当前的根上。此时 $1$ 到根的路径可以看做一个点（如图示）。那么我们发现只要与红点直接相连的子树中能够消完就可以使心最终停到该位置。我们在 dfs 的过程中维护与红点相连的最大子树。但是当要 dfs 的儿子是重儿子的时候我们应该用当前节点的次重儿子来更新。时间复杂度 $O(Tn)$。

---

Code

int ans[N],dep[N];
inline void dfs2(int u,int fa,int hs)
{
    dep[u]=dep[fa]+1;int hhs=siz[hs]>siz[son[u]]?hs:son[u];
    if(f[hhs]<=n-dep[u]-siz[hhs]) ans[u]=(n-dep[u]+1)&1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;if(v==fa) continue;
        int t=(v==son[u])?son2[u]:son[u];
        dfs2(v,u,siz[hs]>siz[t]?hs:t);
    }
}