AtCoder ABC 290 F Maximum Diameter

标签: at

题意

给定一个长度为 的序列 定义如下:

对于所有有 个节点的树,满足第 个节点的度数为 及为所有这样树的直径的最大值。

给定一个 ,求所有长度为 的序列 之和。

由于有多组询问,单次询问时间复杂度必须小于

解法

首先,一棵有 个节点的树有 条边,故 ,且

考虑如何从 求出 。先从链的情况考虑,这时有 由两个 组成,且 。对于其他 ,可以理解成一些 变成了 ,并且把多余的 加到了其他非 的地方,反映到图上就是原来的链中的一些度为 的节点被删除,又重新连到了其他原来非 的节点上,变成了叶子。自然,每多一个 ,直径就小 ,故设序列 个,则 。(有点抽象,自己画图理解)

故枚举 的个数为 的答案为 。其中 为直径, 为所有的 位置的方案数, 为把多余的 分配到其他 个位置的方案数(插板法)。

所以总答案为:

然而这样仍然是 的。问题在于如何快速计算那两个 sigma。以 为例,它的相当于有 个蓝色球和 个红色球,选 个蓝色球和 个红色球的方案数,即是 个球中选择 个球的方案数,也就是

故答案为

void solve()
{
    int n;
    cin >> n;
    if (n == 2) {
        cout << 1 << endl;
        return ;
    }
    mint ans = (n + 1) * binom(2 * n - 3, n - 1);
    ans -= n * binom(n * 2 - 4, n - 2);
    cout << ans.val() << endl;
}