CF1517F - Reunion

Posted on Edited on In

CF1517F - Reunion

题目大意

对于一棵树，树上每个节点颜色在在黑白之间均等随机

定义r: 从某一个点 \(u\) 开始， \(r\) 为使得距离 \(u\) 在 \(r\) 以内的点均为均为黑点的最大距离

求 \(r\) 的期望，全黑和全白的情况 \(r\) 特殊处理

模型转化

当然是期望转概率，枚举 \(d\) ，计算 \(\max\{r\}\ge d\) 的概率

然而 \(\exists r\ge d\) 并不好算，于是算 \(\nexists r\ge d\) 的概率

看成是用白点去覆盖整棵树，每个白点可以覆盖距离 \(d\) 以内的所有点

dp

令 \(dp_{u,i}\) 表示当前 \(u\) 的子树内，

\(i\ge 0\) ，能够向上额外延伸 \(i\) 的距离

\(i<0\) ，还需要一个距离为 \(-1-i\) 的白点伸进去覆盖它

合并可能存在的问题？

如果 \(u\) 子树内即有点伸出去又有点没有被覆盖？

那么记录没有被覆盖的点

因为在最优情况里，这个点一定要被另一个节点覆盖

而那个去覆盖它的点，显然比当前节点延伸出去部分覆盖的范围更大

因此 \(u\) 延伸出去的部分没有用

\[\ \]

第二维出现的个数为 \(O(dep)\) ，借用树形背包的复杂度分析，因此单次复杂度上限为 \(O(n^2)\) ，实际完全不满

总复杂度为 \(O(n^3)\)

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=310,P=998244353;
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

int n,d,m;
vector <int> G[N];
int dp[N][N*2],g[N*2],D[N];
vector <int> tmp;
void dfs(int u,int f) {
	// n+1 为基准偏移
	rep(i,0,m) dp[u][i]=0;
	dp[u][n+d+2]=1,dp[u][n]=1;
	for(int v:G[u]) if(v!=f) {
		dfs(v,u);
		cmax(D[u],D[v]+1);
		rep(i,0,m) g[i]=dp[u][i],dp[u][i]=0;
		tmp.clear();
		rep(i,0,m) if(dp[v][i]) tmp.pb(i);
		rep(i,0,m) if(g[i]) {
			for(int j:tmp) {
				if(max(j-n-2,i-n-2)>=max(n-i,n-j)) dp[u][max(i,j)]=(dp[u][max(i,j)]+1ll*g[i]*dp[v][j])%P;
				else dp[u][min(i,j)]=(dp[u][min(i,j)]+1ll*g[i]*dp[v][j])%P;
			}
		}
	}
	rep(i,0,m) g[i]=dp[u][i],dp[u][i]=0;
	rep(i,1,n) dp[u][i-1]=g[i];
	rep(i,n+2,m) dp[u][i-1]=g[i];
	dp[u][n+1]+=g[n+1],Mod1(dp[u][n+1]);
}

int main(){
	n=rd(),m=n*2+2;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	int all=qpow(2,n),ans=0;
    // d枚举到n-1，正好抵消了n 和 -1的贡献
	for(d=1;d<n;++d) {
		dfs(1,0);
		int s=all;
		rep(i,n+1,m) s-=dp[1][i],Mod2(s);
		ans=(ans+s)%P;
	}
	ans=ans*qpow(all)%P;
	printf("%d\n",ans);
}