2020 China Collegiate Programming Contest, Weihai Site 补题

本文主要是介绍2020 China Collegiate Programming Contest, Weihai Site 补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

C - Rencontre
G - Caesar Cipher

补题链接

C - Rencontre

题目描述：

给出一棵 $n$ 个节点的带权树，现在有三组数量分别为 $m_i$ 的点集，现在从每组中等概率的从中各选一个点（三组相互独立），得到一个三元组 $(a, b, c)$ ，并在树上找一个点 $u$ ，满足 $u$ 到三点的树上路径和最小，求期望路径长度

$\leq n \leq 2 \cdot 10^5,1 \leq w \leq 1000,1 \leq m_i \leq n$

solution:

设 $f(a,b,c)=min_{u \in T}(dist(a,u)+dist(b,u)+dist(c,u))$

对于三元组 $(a, b, c)$ 来说， $f (a, b, c)$ 是固定的，可以表示为 $f(a,b,c)=\frac 1 2(dist(a,b)+dist(b,c)+dist(a,c))$

$E(f(a,b,c))=E(\frac 1 2(dist(a,b)+dist(b,c)+dist(a,c)))=\frac 1 2E(dist(a,b))+\frac 1 2 E(dist(b,c))+\frac 1 2E(dist(a,c))$

也就是说三个点两两之间的路径会产生贡献

有了上述结论，我们根据期望的一般套路之一，根据边的贡献线性相加期望

当且仅当一条边所在的内外两颗子树中存在不同点集的节点时，才会产生贡献

其实我们不需要直到上述结论也可以分析出来，一条边的如果有贡献，那么将其断开后两棵树之间一定存在不同点集的点

考虑维护子树中存在的各个点集的点的个数，设 $s z (u, i)$ 代表子树 $u$ 中类型 $i$ 的点集的个数，对于一条边 $e (u, v, w)$ （u 更靠近根节点）来说，它的贡献是 $\frac {\sum_i \sum_{j!=i} sz(v,i) \cdot (m_j-sz(v,j)) \cdot m_k [i!=k \& j!=k]} 2$