FJOI 树的重心题解

标签：rt 子树 重心 int 题解 FJOI 节点 size

从零开始暴切省选题

题意简述

给定一个 \(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\)，尤其容易忘记。

总结

对于树上与子树或者数量有关问题，一般可以考虑树上 \(DP\)，视情况可以在状态中存储子树大小，子树形态等信息，可以灵活运用计数原理，尤其在子树合并过程中。

标签：rt,子树,重心,int,题解,FJOI,节点,size
From： https://www.cnblogs.com/George-Pig-Orz/p/17607673.html