染色（color）

有 $n$ 个点的一棵树，一开始所有节点颜色为 $0$。

有 $m$ 次操作，第 $i$ 次操作会在 $[0,d_i]$ 中均匀随机选择一个数 $r$，并将距离 $x_i$ 不超过 $r$ 的所有节点颜色染色为 $i$ 。

求树上同色连通块数量期望。

$n,m\le 2000$ 。

先对答案做有转化：

$$\begin{aligned}\mathbb E[同色连通块个数]&=1+\mathbb E[\sum_{e(u,v)}[c_u\ne c_v]]\\ &=1+\sum_{e(u,v)}\mathbb E[[c_u\ne c_v]]\\ &=1+\sum_{e(u,v)}\text{Pr}[[c_u\ne c_v]] \end{aligned}$$

因此，我们只需要对于每一条边 $e(u,v)$ ，求出其两端不同色的概率。

依次考虑所有操作，对于操作 $i$，我们想要更新 $p_{e(u,v)}$ 。

那么对于每一条边 $(u,v)$ ，有如下三种可能：

1. $u,v$ 均被覆盖，设概率为 $P_1$。
2. $u,v$ 其一被覆盖，设概率为 $P_2$。
3. $u,v$ 均未覆盖，设概率为 $P_3$。

可以发现，新的 $p_{e(u,v)}$ 应该是这三种情况的带权和，所以我们要看这三种情况分别的权：

1. 此时这一条边被强制覆盖，会产生 $0$ 的贡献，因此这一项为 $0\times P_1=0$。
2. 此时这一条边一定会有 $1$ 的贡献，因此这一项为 $1\times P_2=P_2$ 。
3. 此时这一条边不会产生任何变化，因此这一项为 $p_{e(u,v)}\times P_3$ 。

于是，我们只需要求出 $P_1,P_2,P_3$ ，就可以完成更新。

我们当然可以暴力：枚举 $r\in[0,d_i]$ ，然后直接模拟，从而获得 $P_1,P_2,P_3$ 。复杂度 $\mathcal{O}(n^2m)$ ，可以获得 $50\%$ 的分数。

不过我们有更聪明的方法：设 $t=\min\{\text{dist}(x_i,u),\text{dist}(x_i,v)\}$ ，则情况 $2$ 发生当且仅当 $r=t$ ，于是 $P_2=\frac{1}{d_i+1}$ ，情况 $1,3$ 同理，分别为 $P_1=\frac{d_i-t}{d_i+1},P_3=\frac{t}{d_i+1}$ 。

于是我们就可以在 $\mathcal{O}(nm)$ 的时间内解决此题（并且看起来可以优化到 $\mathcal{O}(m\log n)$）。