「Codeforces 1097G」Vladislav and a Great Legend

Codeforces 1097G. Vladislav and a Great Legend

当时不会做

题意

给定一棵 $n$ 个点的树

对于每个非空的点集 $X\subseteq {1,2,\dotsc,n}$，定义 $f(X)$ 表示最少的能让点集 $X$ 联通的边的数量

求

$$
\sum_{X\subseteq {1,2,\dotsc,n},X\ne \varnothing} (f(X))^k
$$

模 $10^9+7$

$n\le 10^5,k\le 200$

---

做法

先考虑 $X$ 是树上一个联通子树的点集怎么做

令 $f_{i,j}$ 表示以 $i$ 为根的子树，选择了 $i$ 的所有方案的边数的 $j$ 次和

直接二项式展开，合并两个子树是 $\mathcal O(k^2)$ 的，总复杂度 $\mathcal O(nk^2)$ 无法通过此题

考虑令 $f_{i,j}$ 表示以 $i$ 为根的子树，选择了 $i$ 的所有方案的边数的 $j$ 阶下降幂的和

对于下降幂我们有

• $$
  \begin{align}
  (x+1)^{\underline n} & = n! \binom{x+1}{n} \
  & = n!\left(\binom{x}{n}+\binom{x}{n-1}\right) \
  & = x^{\underline n} + n\times x^{\underline {n-1}}
  \end{align}
  $$

• $$
  \begin{align}
  (x+y)^{\underline n} & = n! \binom{x+y}{n} \
  & = n! \sum_{i=0}^n \binom{x}{i} \binom{y}{n-i} \
  & = n! \sum_{i=0}^n \frac{x^{\underline i}}{i!} \times \frac{y^{\underline {n-i}}}{(n-i)!} \
  & = \sum_{i=0}^n \binom{n}{i} x^{\underline i} y^{\underline {n-i}}
  \end{align}
  $$

因此我们可以 $\mathcal O(k)$ 地加入一条边和 $\mathcal O(k^2)$ 地合并两个子树

总复杂度还是 $\mathcal O(nk^2)$ 的，无法通过

由于下降幂的性质，当以 $i$ 为根的子树中的点数不大于 $j$ 时，$f_{i,j}=0$

我们可以记 $size_i$ 表示以 $i$ 为根的子树的点数，每次合并严格 $\mathcal O(min{size_x, k}, min{size_y, k})$ 地合并两个子树 $x, y$，注意不能包含 $min{size_x,k}^2$

合并两个相邻子树 $x,y$ 时，我们选出 $x$ 的子树中 dfs 序最大的 $k$ 个点和 $y$ 的子树中 dfs 序最小的 $k$ 个点，这样每个点最多会对前后 $2k$ 个点形成贡献，于是总复杂度是 $\mathcal O(nk)$

最后用斯特林数

$$
x^k = \sum_{i=0}^k
\begin{Bmatrix} k \ i \end{Bmatrix}
x^{\underline{i}}
$$

复原出 $k$ 次幂和即可

接下来考虑不是联通子树的情况

定义叶子是联通子树上度为 $1$ 的点，可以发现一个联通子树需要计算 $2^a$ 次，其中 $a$ 是非叶子数量

统计 $i$ 处的答案时，若方案包含了至少两个 $i$ 的儿子， $i$ 就不是叶子，则需要乘系数 $2$，这可以全部计算，最后减去只含一个儿子的情况

做完 $i$ 之后，只要方案包含了至少一个儿子，由于 $i$ 的父亲必须选择，$i$ 就不是叶子，因此把除了 $i$ 单个点的方案都乘 $2$ 即可

---

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, K = 202, P = 1000000007;
int n, k, num, Ans, ans[K], p[K], C[K][K], S[K][K], siz[N], h[N], e[N<<1], pre[N<<1], f[N][K];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void dfs(int u, int fa=0){
	f[u][0]=1;
	for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa){
		dfs(e[i], u), siz[u]+=siz[e[i]];
		for(int j=min(siz[u], k); j; --j){
			f[e[i]][j]=(f[e[i]][j]+(ll)f[e[i]][j-1]*j)%P;
			ans[j]=(ans[j]-f[e[i]][j]+P)%P;
		}
		++f[e[i]][0];
		for(int j=min(siz[u], k); ~j; --j){
			f[u][j]=(ll)f[u][j]*f[e[i]][0]%P;
			for(int t=max(j-siz[e[i]], 0); t<j && t<=siz[u]-siz[e[i]]; ++t)
				f[u][j]=(f[u][j]+(ll)f[u][t]*f[e[i]][j-t]%P*C[j][t])%P;
		}
	}
	for(int i=0; i<=k && i<=siz[u]; ++i) f[u][i]=f[u][i]*2%P;
	f[u][0]=(f[u][0]-1+P)%P;
	for(int i=0; i<=k && i<=siz[u]; ++i) (ans[i]+=f[u][i])%=P;
	++siz[u];
}
int main() {
	read(n), read(k);
	C[0][0]=S[0][0]=p[0]=1;
	for(int i=1; i<=k; ++i) p[i]=p[i-1]*2%P;
	for(int i=1; i<=k; ++i) for(int j=0; j<=i; ++j){
		C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%P;
		if(j) S[i][j]=(S[i-1][j-1]+(ll)j*S[i-1][j])%P;
	}
	for(int i=1, x, y; i<n; ++i) read(x), read(y), add(x, y), add(y, x);
	dfs(1);
	for(int i=0; i<=k; ++i) Ans=(Ans+(ll)ans[i]*S[k][i])%P;
	return printf("%d", Ans), 0;
}