题目概述
给定一棵$n$个节点的树，现在删掉$k$条边再加上$k$条边再成为一棵树，问总方案数。
数据范围
分析与解
这道题很好体现了两个基本问题——树的删边和树的计数。
对于树的删边问题，我们考虑删除$k$条边后形成的$k+1$个连通块，记它们的大小为$s[1],s[2],…,s[k+1]$，为了计数方便，我们把这些连通块都抽象为一个点，那么这些点相互连接，需要枚举一个点度数，所以我们的方案数应该是
出现了点度数，我们不妨用Prufer序列的性质来化简这个式子（具体知识见下文），我们可以得到上式为：
那么问题来了，其实$n^{k-1}$并不难算，关键是我们很难枚举所有的连通块大小为这个s序列的所有树的形态。于是我们谋求问题的转化：
上面这个式子把$n^{k-1}$单提到外面后，剩下的$\sum$等价于我将原先这个树切了$k$条边，剩下的连通块恰好选1个点的总方案数。**恰好选一个点**这件事正是对于这个$\prod$
而这个问题就可以用树形DP来解决了。记$dp[x][y][0/1]$表示$x$的子树，一共删$y$条边，且$x$节点所在的连通块是否选中了点时的方案数。其状态转移可以在DFS时逐一添加子树来计算，具体转移见如下代码。
值得一提的是，根据出题人的讲评，这个DFS过程乍一看是$O(nk^2)$的，实际上是$O(nk)$的，因此可以通过。
代码
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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
#define MAXN 50100
struct node {
int u,v;
node *nnext;
} pool[MAXN<<1],*h[MAXN<<1];
int cnt=-1;
void addedge(int u,int v) {
node *p=&pool[++cnt];
p->v=v,p->nnext=h[u],h[u]=p;
node *q=&pool[++cnt];
q->v=u,q->nnext=h[v],h[v]=q;
}
const int MOD = 998244353;
LL dp[MAXN][110][2];
LL quick_pow(LL a,LL b) {
LL ret=1;
while(b) {
if(b & 1)ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int siz[MAXN];
LL tmp[220][2];
int n,k;
void get_dp(int u,int fa) {
int v;
siz[u]=1;
dp[u][0][1]=dp[u][0][0]=1;
for(node *p=h[u]; p; p=p->nnext) {
v=p->v;
if(v==fa)continue;
get_dp(v,u);
memset(tmp,0,sizeof(tmp));
for(int i=0; i<siz[u] && i<=k; i++) {
for(int j=0; j<siz[v] && i+j<=k; j++) {
tmp[i+j][0]=(tmp[i+j][0]+dp[u][i][0]*dp[v][j][0]%MOD+MOD)%MOD;
tmp[i+j][1]=(tmp[i+j][1]+dp[u][i][1]*dp[v][j][0]%MOD
+dp[u][i][0]*dp[v][j][1]%MOD+MOD)%MOD;
if(i+j==k)continue;
tmp[i+j+1][0]=(tmp[i+j+1][0]+dp[u][i][0]*dp[v][j][1]%MOD+MOD)%MOD;
tmp[i+j+1][1]=(tmp[i+j+1][1]+dp[u][i][1]*dp[v][j][1]%MOD+MOD)%MOD;
}
}
memcpy(dp[u],tmp,sizeof(tmp));
siz[u]+=siz[v];
}
}
int main() {
LL ans=1;
int u,v;
n=mread(),k=mread();
for(int i=1; i<n; i++) {
u=mread(),v=mread();
addedge(u,v);
}
get_dp(1,0);
printf("%lld\n",dp[1][k][1]*quick_pow(n,k-1)%MOD);
return 0;
}
|
Prufer序列
基本概念
对于一个$n$个节点的标号树，其Prufer序列是惟一的，长度为$n-2$。因此可以用于树的形态计数等问题。
其构造方法如下：
①选择当前树中编号最小的叶子，将其删除
②将刚才删除的叶子的父节点加入到序列中
③重复前两步，直到树为空
基本性质
根据Prufer序列的构造方法，不难看出以下的性质：
一、一个点的度数 = 其在Prufer序列中出现次数 + 1
二、n个点的无根标号树形态总数为 $n^{n-2}$
这一条原因是我们可以枚举Prufer序列，而每一个位置可以在$[1…n]$中任取
三、n个点的有根标号树形态总数为$n^{n-1}$
其实就是第二条再枚举根节点。
四、n个点的无根标号树形态总数，要求第$i$个点的度数为$d_i$
这个排列组合相当于我假设$i$对应的$d_i$个标号都是不同的，所以一共有$(n-2)!$种排法，然后再”内部去重”，把内部的排列消除掉，所以就有了分母的连乘式。