[25NOV] 做题记录

性质 B：给定树 $T$，其最大独立集（MIS）是唯一的，记为 $I$。
我们要算：随机算法返回的计数 $c$ 恰好等于 $|I|$ 的概率。

算法是：

所有点白色，$c=0$；
反复：从所有白点中等概率选一个 $u$，把 $u$ 和所有仍为白色的邻居染黑，c++；
无白点时停，返回 $c$。

（注意：最后选出来的是某个极大独立集的大小，不保证最大。）

经典套路：
这类“每次在剩余元素里随机选一个做决策”的过程，可以等价为：

先给所有点一个独立的随机实数权值（优先级）$w_v \sim U(0,1)$，
按权值从小到大依次扫：如果当前点没有已选邻居，就把它选入集合。

所以我们只需要研究：

对随机权值 $w$，贪心算法得到的独立集等于唯一 MIS $I$ 的概率。

记 $O = V \setminus I$（不在 MIS 里的点）。

首先两件显然的事：

因为 $I$ 是最大独立集，所以它也是极大独立集：
$\forall u\in O$，都有邻居在 $I$。否则可以把 $u$ 加进去得到更大独立集。
所以 $I$ 是支配集：每个 $O$ 点至少连着一个 $I$ 点。
$I$ 独立：任意两点 $v_1,v_2\in I$ 没有边。

我们想要：贪心选出的集合恰好为 $I$，即：

没有 $O$ 点被选入；
所有 $I$ 点都被选入（否则选不满 $|I|$ 就不可能是 MIS，且唯一性也会炸）。

考虑某个 $u\in O$。

要阻止 $u$ 被贪心选中，必须在它“轮到被考虑”之前，已经有某个邻居被选了来把它“染黑”。

但注意：被选中的点最终必须都在 $I$，否则结果就不是 $I$。

因此：对于一个合法的随机权值配置（即最终得到 $I$），每个 $u\in O$ 都必须满足：

在 $\{u\} \cup (N(u) \cap I)$ 中，最小权值的点属于 $I$，而不是 $u$。

否则，如果 $w_u$ 比所有邻居的 $I$-点都小，那在它被扫描时没有已选邻居，它就会被选进集合，矛盾。

进一步，还要排除“被别的 $O$ 点挡住”的情况：
如果最小的是某个 $O'$，那 $O'$ 本身会被选中（因为没人挡它），又矛盾。
所以在“成功的”权值配置下，每个 $O$ 点的“拦截者”必须是 $I$ 点。

于是得到充分必要条件（在唯一 MIS 条件下）：

贪心输出 $I$ 当且仅当
对所有 $u\in O$，有
$$ w_u > \min_{v \in N(u)\cap I} w_v. $$

换句话说，至少有一个连着它的 $I$-点比它更早出现，从而把它杀掉。

而一旦这条对所有 $u\in O$ 成立，由于：

$I$ 自身独立，不会互相杀；
每个 $O$ 的杀手来自 $I$，没有 $O$ 被选入；
$I$ 是极大独立集（支配所有点）；

贪心一定正好选出所有 $I$，不多不少。

这个条件只依赖「$I$ 与每个 $O$ 的邻接关系」和权值顺序，
不再直接看 $O$-$O$ 边——因为那些边一旦起作用就会导致 $O$ 被选，已经被我们排除了。

现在只关心：图上 $I$ 与 $O$ 之间的边。

构造图 $H$：

顶点仍是 $V$；
只保留所有 $I$-$O$ 边，删去 $I$-$I$（本来就没有）和 $O$-$O$ 边。

原图是树 ⇒ 去掉一些边后 $H$ 是一片森林。
每个连通块只在 $I$ 与 $O$ 之间交替。

而我们的成功条件是：

对每个 $u\in O$，$w_u > \min_{v\in N_H(u)} w_v$。

关键：每个 $u\in O$ 的邻接 $I$-点都在这片 forest 里，耦合关系只发生在同一个连通分量中。
不同连通分量的权值独立，条件也独立 ⇒
总概率 = 各连通分量成功概率的乘积。

所以我们只需求：

在一个连通的 $I$-$O$ 树上，这些不等式成立的概率。

我们对每个连通分量：

随便选一个 $I$-点做根 $r$。
把它看成根在 $I$ 侧的二叉/多叉树，层次 I-O-I-O…

对这个树做从叶到根的 DP。

对一个 $I$-点 $v$ 定义 $G_v(x)$：
在「父亲那边给的约束已经满足」前提下，在 $w_v = x$ 时，它整棵子树中所有不等式成立的条件概率。
（你可以理解为：从 $v$ 往下那块，只看局部约束后留下来的“合法权值配置密度”。）
对一个 $O$-点 $u$ 定义 $M_u(x)$：
在「与它连着的父亲 $I$-点权值为 $x$」时，整棵以 $u$ 为根的子树满足所有约束的条件概率。

因为所有约束和分布都是多项式/积分可写的形式，这两个函数都将是关于 $x$ 的多项式（模意义下）。

I 点转移

若 $v$ 是 $I$ 点，它的子节点全是 $O$ 点 $u$：

条件是：所有这些 $u$ 的子树在给定 $w_v=x$ 下都合法；
子树独立 ⇒
$$ G_v(x) = \prod_{u \text{是 }v\text{的子 }O} M_u(x). $$

O 点转移

设 $u$ 是 $O$ 点，有父 $I$-点权值 $x$，子 $I$-点为 $v_1,\dots,v_k$。

约束只有两个部分：

对这个点本身：
$$ w_u > \min(x, w_{v_1},\dots,w_{v_k}) $$
每个子 $I$-点 $v_i$ 的子树约束，用 $G_{v_i}(w_{v_i})$ 表达。

权值独立均匀，我们要算：
$$ M_u(x) = \mathbb{P}\Big( w_u > \min(x,w_{v_1},\dots,w_{v_k}),
\bigwedge_i \text{子树 }i\text{合法} ,\Big|, w_{\text{parent}}=x \Big). $$

对每个子 $v_i$，它的权值 $y_i$ 均匀于 $[0,1]$，子树合法概率为 $G_{v_i}(y_i)$。
定义
$$ T_i(t) = \int_t^1 G_{v_i}(s),ds, $$
表示「在 $y_i \ge t$ 时子树合法的积分贡献」。

我们先计算在忽略 $u$ 的限制的前提下，合法方案出现的概率 $C$。

然后再减去再方案合法的前提下，不满足 $u$ 的限制的概率。

前者是显然的 $C = \prod_{i=1}^k T_i(0)$

后者我们需要 $\exists v\in I, w_u < w_v$ ①，保证 O 点 $u$ 先于 I 点 $v$ 被选。

但是我们发现，仅仅是存在并不正确，考虑 I-O-I 的情况下，我们把两个 I 分别称为 $v_1,v_2$，且 $w_{v_1} < w_{v_2}$。

如果 $w_{v_1}<w_u<w_{v_2}$，虽然 $u$ 的限制的确被满足了，但我们的方案就不合法了。因为 $v_1$ 被选后 ban 了 $u$，$u$ 无法被选，而我们期望 $v_1,u,v_2$ 均被选。

所以上面条件①的存在应当改成任意。

那么答案就是

$$ M_u(x) = C - \int_0^{x} \prod_{i=1}^k T_i(t),dt, $$

对该连通分量的根 $I$-点 $r$：

没有父亲约束，只需要对 $w_r$ 在 $[0,1]$ 上积分：
$$ P_{\text{comp}} = \int_0^1 G_r(x),dx. $$

所有都是多项式，用模意义的积分（系数除以 $k+1$）即可。