本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-05 21:13:59

:::::info[题目基本信息] 考察：贪心（$2858$）。
题目简介：
$t$ 组数据，每组数据给你一棵 $n+1$ 个点的有根树，根为 $0$，有一个关键点位于这棵树的任意非根节点，给定 $\{a_n\}$，表示 $\forall i\in[1,n]$，$i$ 点为关键点的概率为 $\dfrac{a_i}{\sum_{j=1}^na_j}$，定义一次操作为：

• 选择一个已被操作的点的儿子，对其操作。

初始时 $0$ 点已被操作，问操作次数的期望值的最小值是多少。
数据范围：

• $1\le t,n,\sum n\le 2\times 10^5$
• $\forall i\in[1,n],a_i\ge 1$
• $\sum_{i=1}^na_i\le 10^8$ ::::: 注意到这个题我们不能直接贪心选更优的点，因为更劣的点下可能有特别优的点，但是我们注意到这时选完这个劣点下一步肯定会直接选这个优点，这时我们就可以直接合并这两个点。
  现在我们要对“优”进行定义。
  我们一开始每个点的权值不妨直接设为 $a_i$，最后的时候再除以一个 $\displaystyle\sum_{i=1}^na_i$ 即可，那么合并后的点的权值是什么呢？
  这时，这个大点会对操作次数贡献 $2$，那么我们不妨考虑邻项交换法，令 $x$ 点的实际点数为 $b_x$，实际点的编号构成序列 $\{id_{x,b_x}\}$，对 $y$ 点做相同的定义。
  这时我们要求 $x$ 点在前，那么我们得到： $$(\sum_{i=1}^{b_x}ia_{id_{x,i}})+(\sum_{i=1}^{b_y}(i+b_x)a_{id_{y,i}})<(\sum_{i=1}^{b_y}ia_{id_{y,i}})+(\sum_{i=1}^{b_x}(i+b_y)a_{id_{x,i}})$$ 解得：$\dfrac{\sum_{i=1}^{b_x}a_{id_{x,i}}}{b_x}>\dfrac{\sum_{i=1}^{b_y}a_{id_{y,i}}}{b_y}$。
  这样我们就容易得到任意点的权值了。
  后面就可以直接用堆和并查集维护了，细节还是见代码。
  code