题目大意
对一棵树的节点染色。初始时每个点都染成颜色 $0$,然后进行 $m$ 轮操作。第 $i$ 轮操作:从 $[0,d_i]$ 中随机选出一个整数 $d$,将距离点 $x_i$ 不超过 $d$ 的点染成颜色 $i$。求最后「同色连通块」的个数的期望。
分析
期望问题的做法一般是
利用期望的线性性将所求的随机变量分解
问题的难点正在于写出同色的连通块的个数的表达式。
同色连通块的个数 = 两端点颜色不同的边的数目 + 1
令 $p^{i}[u][v] (u<v)$ 表示第 $i$ 轮操作后边 $(u,v)$ 两端颜色不同的概率, $\text{dis}^{i}[u]$ 表示 $x_i$ 与 $u$ 的距离。
则 $$p^{i+1}[u][v] = \frac{\text{dis}^{i+1}[u]}{d_{i+1}+1}p[u][v] + \frac{1}{d_{i+1}+1}$$Implementation
#includeusing namespace std;const int N=2e3+5;double dp[N][N];vector g[N];int x, d;void dfs(int u, int fa, int dis){ if(dis>d) return; for(auto v: g[u]) if(v!=fa){ int _u=min(u, v), _v=max(u, v); dp[_u][_v]=(dp[_u][_v]*dis+1)/(d+1); dfs(v, u, dis+1); }}int main(){ int n, m; cin >> n >> m; for(int i=1; i > u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i=0; i > x >> d; dfs(x, x, 0); } double res=0; for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) res+=dp[i][j]; // cout << res+1 << '\n'; printf("%.10f\n", res+1); return 0;}