FJOI 树的重心题解

来源：博客园发布时间：2023-08-05 11:27:46

从零开始暴切省选题

题意简述

给定一个 $n$ 个点的树，每个点的编号从 $1$ 至 $n$，问这个树有多少不同的连通子树，和这个树有相同的重心。

分析

1 求重心

首先要明确重心的定义。题目中给出：删掉某点 $i$ 后，若剩余 $k$ 个连通分量，那么定义 $d(i)$ 为这些连通分量中点的个数的最大值，所谓重心，就是使得 $d(i)$ 最小的点 $i$。这句话翻译成人话就是：给定一棵无根树，令任意 $u$ 为根，使得最大子树最小的 $u$ 即为该树的重心。由这个定义，我们可以明确重心的求法。先假设节点 $1$ 为根，对于每一个节点 $u$，求它的所有子树大小，并取其最大值，与已存储的根的最大子树比较，如果节点 $u$ 的最大子树更小，那么更新根节点 $rt\leftarrow u$。这在搜索回溯时处理即可。特别注意的是，搜索时因为程序需要钦定 $1$ 为根节点，因此在递归至其他节点时要注意：如果以 $u$ 为根，则还有一棵大小为 $n-size_u$ 的子树（$n$ 为节点数），这也要计入子树中。

(资料图)

inline void getr(int u, int fa) {    siz[u] = 1;    dp[u] = 0;    for(auto v : G[u]) {        if(v != fa) {            getr(v, u);            siz[u] += siz[v];            dp[u] = max(dp[u], siz[v]);        }    }    dp[u] = max(dp[u], n - siz[u]);    if(dp[rt] > dp[u] or rt == 0) {        rt = u;    }}

2 分类

求出重心后注意到题目提示 基于以上定义，一个树的重心可能会有一个或者两个。这提示我们要进行分类讨论。那么分类的标准是什么呢？注意到上文提到的重心的定义中出现了最大子树最小这一 $min-max$ 条件，稍加推导就可以得出重心的一条重要性质：点 $u$ 是树的重心 $\Leftrightarrow$ $u$ 的所有子树大小不超过 $\lfloor\dfrac{n}{2}\rfloor$（证明···自己找，网上很多的）。

然后就可以发现，如果有两个重心，那个两个重心所在的子树大小相等，均为 $\dfrac{n}{2}$，所以设已求得的重心为 $rt$，如果满足 $size_rt\times2==n$，则树有两个重心；否则树只有一个重心。

3 DP与转移

根据题中求联通子树个数这个要求及答案对 $1e4+7$ 取模可以猜测，解法应为树上 $DP$。因此考虑状态。在已知两个子树的情况下，如果要合并答案可以知道，应该用乘法原理令两个子树选取的节点数相乘再求和，所以 $f$ 状态要能够记录选取的节点数这一关键信息。于是发现可以定义状态 $f_{u,i}$ 表示以 $u$ 为根的子树，取 $i$ 个节点的方案数。其中取 $i$ 个节点可以解释为这棵联通子树里有 $i$ 个节点。

考虑在 $dfs$ 过程中求解 $f_{u,i}$（以下默认 $u$ 为当前子树的根节点）。先求 $size$ 数组，可知现在已合并到 $u$ 的子树里的节点个数最多为 $size_u$，设要合并的子树根节点为 $v$，则节点最多有 $size_v$ 个。由上文的分析不妨把子树 $u$ 和子树 $v$ 分开枚举，分别枚举 $i$ 和 $j$，则可以更新 $f_{u,i+j}$ 的答案。注意到由于更新时要用到原 $f$ 数组的数据，于是用一个 $res$ 数组暂存结果，等到全部转移完再复制到 $f_u$ 中。

由乘法原理可得对于 $res_{i+j}$ 有如下式子：

\[res_{i+j}=\sum_{i=1}^{size_u}\sum_{j=0}^{size_v}f_{u,i}\times f_{v,j}\]

而初始化条件即为 $f_{u,0}=f_{u,1}=1$。

4 答案求解

由 $2$ 中的分类，以重心数量为依据分开处理。

如果重心有两个则较为简单。首先求重心时已求得一个重心，考虑到重心性质：如果有两个重心则两个重心相邻，可以直接枚举与 $rt$ 相邻的节点 $v$，如果 $size_v=size_rt=\dfrac{n}{2}$，则 $v$ 为另一个重心。定义 $3$ 中的 $dfs$ 为 $dfs(u,fa)$， $u$ 为当前节点，$fa$ 为父节点，则直接 $dfs(rt,v),dfs(v,rt)$ 就可以求出对于两个子树分别成立的 $f$ 数组。然后在 $1\sim n$ 枚举所有可能的树大小， $ans$ 就可以快速地求出了：

\[ans=\sum_{i=1}^{n}f_{rt,i}\times f_{v,i}\]

inline void dfsdptwort(int u, int v) {    memset(ddp, 0, sizeof ddp);    dfs1(u, v);    dfs1(v, u);    for(int i = 1; i <= n; i++) {        ans = (ans + ddp[u][i] * ddp[v][i]) % mod;    }}

如果只有有一个重心，则枚举每个可能的树大小再重复一遍 $dfs$ 中的求解过程就可以了。

inline void dfsdponlyrt(int u) {    memset(ddp, 0, sizeof ddp);    dfs1(u, 0);    for(int i = 1; i <= n; i++) {        memset(ddp[u], 0, sizeof ddp[u]);        s[u] = 1;        ddp[u][0] = ddp[u][1] = 1;        for(auto v : G[u]) {            for(int j = 1; j <= s[u] + s[v]; j++) {                tmp[j] = 0;            }            for(int j = 1; j <= s[u]; j++) {                for(int k = 0; k <= s[v]; k++) {                    if(k * 2 >= i) {                        break;                    }                    tmp[j + k] = (tmp[j + k] + ddp[u][j] * ddp[v][k] % mod) % mod;                }            }            s[u] += s[v];            for(int j = 1; j <= s[u]; j++) {                ddp[u][j] = tmp[j];            }        }        ans = (ans + ddp[u][i]) % mod;    }}

注意，由于有多组数据，每次数组和临时数据都要清空，尤其是用 $vector$ 存储的邻接表用的 $pushback$，尤其容易忘记。