ARC087D Squirrel Migration

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给出一棵 个节点的树。

求使得 最大的排列 的个数。

答案对 取模，，时限 。

首先考虑如何求出 的最大值。

对每条边分别考虑贡献，设两侧的点数分别为 ，则这条边的贡献有上界 。

也可以构造出方案使得每条边的贡献达到上界。

以重心为根，对于每条边而言，深度较大的一侧则为点数较小的一侧。

记 的子树大小为 ，每条边 （ 为较深一侧 ） 都要上下经过各 次。

对于每个点，寻找一个与自己处在根的不同分支的，未匹配的点，进行匹配即可。

（若某个点和同一个分支内的点匹配，则必然不优）

由于根的各个分支大小不超过整棵树的一半，故总能有这样的匹配。

接下来考虑计数。

  • 只有一个重心

记第 个分支的大小为 。（这种情况下允许重心匹配自己）

问题可以转化为 ： 有 个点，点有颜色（同一个分支即为同色），要为每个点连出一个出边（有向边），满足每条边两端不能同色。

考虑容斥， 表示钦定 条边两端同色，其余随意的方案数，则有 ：

接下来看 如何计算。可以先挑出 条同色边，剩余的边随意，方案数是 。

对于第 种颜色，钦定 条同色边的方案数为

将各个颜色的方案卷积（背包）起来即可。复杂度为 。

若利用分治 则可以做到 。

  • 有两个重心

找出连接两个重心的边，两侧的点数都恰好是 。

只需要两侧的点之间随意匹配即可，方案数为 。