One Goal

数学 题解

---

题意:

给你一棵树 $\mathcal T(\mathcal V,\mathcal E)$ 和一个参数 $k$

我们定义 $u\in \mathcal V$ 是序列 $\hat{\mathcal V}$ 的重心 当且仅当点 $u$ 是到 $\hat{\mathcal V}$ 中各点距离和最小的点中编号最小的点 我们记 $f(\hat{\mathcal V})=u$

我们定义 $\mathcal S(\mathcal V,k)$ 表示 所有满足下列条件的序列 $\hat{\mathcal V}$ 的集合:

1. $|\hat{\mathcal V}| = k$
2. $\forall x \in \hat{\mathcal V}$ 有 $x\in \mathcal V$

求 $\sum_{\hat{\mathcal V} \in \mathcal S(\mathcal V,k)} f(\hat{\mathcal V})\mod 998244353$

solution

首先注意 $f(\hat{\mathcal V})\notin \hat{\mathcal V}$ 因为 $f(\hat{\mathcal V})$ 是可能来自于 $\mathcal T$ 上的一条链的

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

$k$ 是奇数

直接考虑一个点 $u$ 作为 重心 的方案数 类似于无标号无根树的技巧 我们容斥直接计算有一棵子树 $\hat{\mathcal T}$ 满足 $|\hat{\mathcal T}\bigcap \hat{\mathcal V}| \geq \lfloor\frac{k}{2}\rfloor$

我们将 $u$ 的子树记作 $\hat{\mathcal T_1},\hat{\mathcal T_2},\cdots,\hat{\mathcal T_m}$ 以 $|\hat{\mathcal T_1}\bigcap \hat{\mathcal V}| \geq \lfloor\frac{k}{2}\rfloor$ 为例 方案的 $\text{EGF}$ 是:

$$e^{|\mathcal V|-1-|\hat{\mathcal T_1}|}\sum_{i\geq \lfloor\frac{k}{2}\rfloor} \frac{(|\hat{\mathcal T_1}|x)^i}{i!}$$
因此 $u$ 作为 重心的贡献的 $\text{EGF}$ 是:
$$ue^{(|\mathcal V|-1)x}(1-\sum_{i=1}^m \mathcal F(|\hat{\mathcal T_i}|x))$$
其中:
$$\mathcal F(x)=\frac{\sum_{j\geq \lfloor\frac{k}{2}\rfloor}\frac{x^j}{j!}}{e^{x}}$$
答案的 $\text{EGF}$ 是:
$$\sum_{u\in \mathcal V} ue^{(|\mathcal V|-1)x}(1-\sum_{i=1}^{m_{u}}\mathcal F(|\hat{\mathcal T_i}|x))$$
考虑怎么算这个东西 我们先把可以提出去的东西提出去:
$$\mathcal G(x)=e^{(|\mathcal V| - 1)x} \sum_{u \in \mathcal V} u(1-\sum_{i=1}^{m_u} \mathcal F(|\hat{\mathcal T_i}|x))$$
我们把后面那个 $\sum$ 抽象出来 等价于求:
$$\sum_{i=1}^{m} b_if(a_ix)$$
其中 $f(x)$ 是一个多项式 我们交换一下求和符号:
$$\sum_{j=0}^k f_jx^j\sum_{i=1}^m b_ia_i^j$$
把后面这个拿出来 设 $\mathcal H(x)=\sum_{j} x^j \sum_{i=1}^m b_i a_i^j$ 继续交换:
$$\mathcal H(x)=\sum_{i=1}^mb_i\sum_{j=0}^k a_i^j x^j=\sum_{i=1}^m \frac{b_i}{1-a_ix}$$
是个套路的问题 可以直接通分 复杂度 $\mathcal O(n\log^2 n)$

最后算答案 就是:

$$\sum_{i=0}^k {n\choose i} i! [x^i]\mathcal G(x)$$

$k$ 是偶数

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

接下来我们单独考虑存在一条路径的情况 我们假设这条路径是 $(u,v)$ 也就是 $u$ 的子树中有 $\frac{k}{2}$ 个点 $v$ 的子树中有 $\frac{k}{2}$ 个结点 尝试对于 $i$ 统计 $i$ 作为重心的次数

考虑枚举一个含有 $i$ 的联通块 联通块内编号 $\geq i$ 把这个联通块看成一个点之后 枚举两棵子树 满足 $\frac{k}{2}$ 个点的 $\text{lca}$ 在该联通块内不在外面的子树 $\hat{\mathcal T_1}$ 内

这样方案数是 $|{\mathcal T_v}|^{\frac{k}{2}}-|\hat{\mathcal T_1}|^{\frac{k}{2}}$ 但是这个联通块不好维护 我们按照编号枚举 用并查集维护即可

这部分特殊处理的复杂度是 $\mathcal O(n\alpha(n))$ 的 总的复杂度是 $\mathcal O(n\log^2 n)$ 复杂度瓶颈在分治 fft 上