[关闭]
@computerkiller 2021-04-03T07:19:05.000000Z 字数 2063 阅读 679

One Goal

数学 题解


题意:

给你一棵树 和一个参数

我们定义 是序列 的重心 当且仅当点 是到 中各点距离和最小的点中编号最小的点 我们记

我们定义 表示 所有满足下列条件的序列 的集合:

solution

首先注意 因为 是可能来自于 上的一条链的

但是来自链的只可能当 因此我们根据 的奇偶性分类考虑

是奇数

直接考虑一个点 作为 重心 的方案数 类似于无标号无根树的技巧 我们容斥直接计算有一棵子树 满足

我们将 的子树记作 为例 方案的 是:


因此 作为 重心的贡献的 是:

其中:

答案的 是:

考虑怎么算这个东西 我们先把可以提出去的东西提出去:

我们把后面那个 抽象出来 等价于求:

其中 是一个多项式 我们交换一下求和符号:

把后面这个拿出来 设 继续交换:

是个套路的问题 可以直接通分 复杂度

最后算答案 就是:

是偶数

我们先把重心唯一的时候的结果算出来 考虑我们限制子树大小小于 这个时候的重心仍然是唯一的 算法和上面的一样 有个细节是 的最低次会被减 2 次 特判掉就可以了

接下来我们单独考虑存在一条路径的情况 我们假设这条路径是 也就是 的子树中有 个点 的子树中有 个结点 尝试对于 统计 作为重心的次数

考虑枚举一个含有 的联通块 联通块内编号 把这个联通块看成一个点之后 枚举两棵子树 满足 个点的 在该联通块内不在外面的子树

这样方案数是 但是这个联通块不好维护 我们按照编号枚举 用并查集维护即可

这部分特殊处理的复杂度是 的 总的复杂度是 复杂度瓶颈在分治 fft 上

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注