题解：CF2071E LeaFall

· · 题解

cnblogs

分类讨论部分参考了现有的一篇题解（怎么想不到呢），自己推了式子。

一个点成为叶子的充要条件是它自己没有被删除，且它的邻居恰好有一个没有被删除。

对下文变量的一些声明：

将点对分类，分别计算贡献：

对于 dis(u,v)=1：

此时两点互为邻居，枚举树上每一条边，贡献为 a_u a_v q_u q_v。这样，第一类贡献就为每条树边的贡献之和。复杂度 O(n)。

对于 dis(u,v)=2：

此时 u 和 v 有一个公共邻居 z，枚举 z，对每个 z 统计它邻居两两贡献。

下式前半部分对应 z 未脱落的情况，此时 u,v 的其他邻居必须全部脱落，且 u,v 本身不脱落；后半部分对应 z 脱落的情况，u 和 v 都恰好剩下一个未脱落的邻居，且 u,v 本身不脱落。对于某个 z 的贡献：

f(z)=(1-p_z)\sum_{u,v} (1-p_u) \frac{a_u}{p_z} \times (1-p_v) \frac{a_v}{p_z}+ p_z\sum_{u,v} (1-p_u)\frac{b_u-a_uq_z}{p_z} (1-p_v) \frac{b_v-a_vq_z}{p_z}

这样子复杂度是 O(deg_z^2) 的，但是由于 2 \times \sum_{i<j} x_ix_j = (\sum x_i)^2-\sum x_i^2，就可以非常容易地优化为 O(deg_z)。我另外开了一个函数算这种形式的式子。

最后把所有 f(z) 累加，就得到了第二类贡献。复杂度 O(n)。

对于 dis(u,v)>2：

计算第三类贡献：

ans=\sum_{dis(u,v)>2} d_ud_v

这样不太好处理，转化为对每个点求贡献，并转化为总贡献减去不合法（距离太小）的贡献，设 sum=\sum_{i=1}^{n} d_i。

\begin{aligned} ans&=\frac{1}{2}\sum_{u=1}^n \sum_{dis(u,v)>2} d_u d_v \\ &=\frac{1}{2} \sum_{u=1}^n d_u (sum- \sum_{dis(u,v) \leq 2} d_v) \end{aligned} \end{equation*}

考虑如何 O(deg_u) 获取里面的和式：

\sum_{dis(u,v) \leq 2} b_v=b_{fa_{fa_u}} + s_{fa_u}+\sum_{v\in son(u)} s_v

第一项即 u 父亲的父亲，第二项包括 u 的父亲以及 u 的父亲的儿子们（包括 u），第三项为 u 的儿子与孙子（即儿子的儿子）。

复杂度 O(n)。

上面的式子是写完代码之后重新推的，虽然检查过但是没准还是有错，欢迎在评论区捉虫。

代码见提交记录，变量名意义和上面式子一致。