0%

「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$ 即可


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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;
}