ARC165E Random Isolation

,

Random Isolation

Description

给定一颗 $n$ 个点的树，如果存在，则随机大于 $k$ 的连通块，随机选择连通块中的一个点，删掉这个点以及相邻的边。期望操作次数。

$k<n\le 100$。2s。

Solution

根据期望的线性性，期望的操作次数为每个点期望的操作次数之和。考虑 $O(n)$ 枚举以每个点为根。

考虑树的一颗子图，子图的节点数为 $n$，相邻的节点数为 $m$，则到达这个子图的概率为 $\dfrac{1}{\dbinom{n+m}{n}}$。所以一个子图的概率只与 $n$ 和 $m$ 相关，类似于树上背包 dp。

这样做是 $O(n^5)$ 的，但观察到 $n+m\le$ 总节点个数，所以常数比较小。能过。

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
80
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 205
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=998244353;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int suf[maxn],isuf[maxn];
int C(int n,int m) {return suf[n]*isuf[m]%mod*isuf[n-m]%mod;}
int iC(int n,int m) {return suf[m]*suf[n-m]%mod*isuf[n]%mod;}
void add(int &x,int y) {x=(x+y)%mod;}
int n,m,ans,f[maxn][maxn][maxn],g[maxn][maxn],siz[maxn],inv[maxn];
vector<int>to[maxn];
void dfs(int x,int pre) {
	siz[x]=1;
	int i,j,k,l,cnt=0;
	f[x][1][0]=1;
	for (auto y:to[x]) if (y^pre) {
		dfs(y,x);
		memset(g,0,sizeof(g));
		for (i=1;i<=siz[x];i++)
			for (j=0;j<=siz[x]-i;j++) {
				add(g[i][j+1],f[x][i][j]);
				for (k=1;k<=siz[y];k++)
					for (l=0;l<=siz[y]-k;l++) {
						add(g[i+k][j+l],f[x][i][j]*f[y][k][l]);
					}	
			}
		siz[x]+=siz[y];
		for (i=0;i<=siz[x];i++) for (j=0;j<=siz[x];j++) f[x][i][j]=g[i][j];
	}
}
signed main(void){
	int i,j,k,x,y;double tmp=0;
	read(n);read(m);
	for (i=1;i<n;i++) {
		read(x);read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for (inv[0]=1,i=1;i<=2*n;i++) inv[i]=power(i);
	for (suf[0]=1,i=1;i<=2*n;i++) suf[i]=suf[i-1]*i%mod;
	isuf[2*n]=power(suf[2*n]);
	for (i=2*n;i>=1;i--) isuf[i-1]=isuf[i]*i%mod;
	for (i=1;i<=n;i++) {
		memset(f,0,sizeof(f));
		dfs(i,0);
		for (j=m+1;j<=n;j++) for (k=0;k<=n-j;k++) {
			add(ans,iC(j+k,j)*f[i][j][k]%mod*inv[j]%mod);
		}
	}
	printf("%lld",ans);
	return 0;
}