Ｂ口罩

太经典的题了，以前这场之后都见过两次了。

考虑钦定 $k$ 条边，然后把这 $k$ 条边删掉，再加入回去，求有多少种树。最后再二项式反演回去即可。

一个结论：有一个 $n$ 个点的森林，其中有 $k$ 个连通块，设每个连通块大小是 $d_i$ ，连边可以形成的树的个数是

$$n^{k-2} \prod d_i$$

考虑 $\text{prufer}$ 序，构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点，把 $1 \dots k$ 写下来，每次找到最小的没有一个点在 $\text{prufer}$ 出现的连通块拿出来，和首项连边。连边的时候会找到当前连通块的一个点去连。序列长度为 $2$ 则直接分别选一个点连。而每个 $1 \dots k$ 的连通块都正好需要选一次点，所以乘上每个连通块的大小。

然后可以发现，$\prod d_i$ 本质上就是把树分成若干个连通块，每个连通块选正好一个点的方案数。所以我们可以 $dp[u][k][0/1]$ 表示当前在 $u$ 选了 $k$ 个连通块出来了，$u$ 所在连通块是否选点。树形 $dp$ 即可。

复杂度根据某经典证明是 $O(n^2)$ 的。

C 了吗

关于这个题的定义：

$$S_u = \sum_{v \in son_u} V_v \\ V_v = S_u + t,t \in[0,k] \cup S_u$$

可以发现 $S$ 是一个类似求子树大小的时候的 $dp$ 的东西。这种东西往往可以差分：

$$V'_u = V_u - S_u = t\\ S_u = \sum_{v \in son_u} (S_v + V'_v) = \sum_{v \in sub_u , v \neq u} V'_v\\ V_u = \sum_{v \in sub_u} V'_v$$

这样一来，$S$ 就只在求 $V’$ 的时候有用，要求的就是有多少种方案使得整个树的 $V’$ 的和为 $s$ 。

每个点的 $V’$ 有两种情况，要么这个点的 $V’$ 是 $[0,k]$ 中任选的一个数，要么是整个子树除了这个点的 $V’$ 的和。那么考虑一个点 $u$ ，如果它是第二种情况，那么它对根的贡献是什么。会发现，每经历一个第一种祖先，这个点的贡献就会翻倍一次。最后，这个点的贡献一定是 $2^kt_u$ 。

考虑每个点本身，写成一个 OGF 的形式，它的贡献是 $1+x^{2^t}+x^{2\times 2^t} + \cdots + x^{k \times 2^t}$ 这个东西。我们不妨设 $F(x) = 1+x+x^2+ \cdots + x^k$ ，考虑每个 $2^k$ 按 $k$ 分类后，就是 $(F(x^{2^k}))^w$ 这个东西，$w$ 是多少个点贡献是 $2^k$ 。考虑算 $F(x)^w$ 再给它的指数乘上 $2^k$ 。直接拿 $\text{exp}$ 做是可以的，但是常数很大，$10^6$ 不一定能过。

考虑我们要算的其实是

$$(\frac{1-x^{k+1}}{1-x})^w \bmod x^S\\ = (1-x^{k+1})^{w} (\frac{1}{1-x})^w$$

前面那个可以二项式定理展开，然后直接写出来，后面那个就相当于做 $w$ 次 $\{1,0,\dots\}$ 的前缀和，这个东西的式子是很容易写出来的

$$\sum_{i}x^i \binom{w+i-1}{w-1}$$

现在我们相当于有很多多项式 $g_0,\dots g_k$ ，需要算出

$$g_0(x^1)g_1(x^2)g_2(x^4)\dots$$

考虑倒着计算这个东西，每次先算出 $g_k(x)$ 然后乘上 $g_{k+1}(x^2)$ ，每次乘法都只暴力 $\frac{S}{2^{k}}$ 项，所以复杂度其实是 $(S+\frac S 2 + \frac S 4 + \cdots)\log S = O(S\log S)$ 的。

注意，每次别把长度开成 $3s$ ，这样会导致 NTT 带两倍的常数。最好每次就开 $2s$ ，然后乘了前两个丢掉 $> s$ 的项再乘，这样常数会小一些。

复杂度 $O(S\log S)$ 。