2021.10.16模拟赛

I will no longer be a transient When I see smiles with tears

2021.10.16模拟赛

A. 区间

区间

经典原题，每次取区间最小值分治即可

B. 树

树

因为期望具有线性性，所以 $u \to v$ 的期望就是 $u \to lca$ $lca \to v$ 的期望之和

所以只需要处理出每个点走到它的父亲和从他父亲走到他的期望即可

走到他父亲 : $up_x=\dfrac{1}{d_x}+\sum\limits_{v \in \operatorname{son}(x)}\dfrac{1+up_v+up_x}{d_x}$

第一部分是直接走向父亲，第二部分是先走向一个儿子然后走回来，化简 $up_x=\sum up_v+d_x$

父亲走到他 ：$down_x =\dfrac{1}{d_{fa_x}}+\dfrac{1+down_{fa_x}+down_x}{d_{fa_x}}+\sum\limits_{v \in \operatorname{son}(fa_x)}\dfrac{1+up_v+down_x}{d_{fa_x}}$

第一部分是直接走，第二部分是走到父亲的父亲然后走回来，第三部分是先走到兄弟然后走回来

两边 DFS 即可

C. 做运动

做运动

按 $t$ 排序一条条加边，直到 $S,T$ 连通跑一下最短路

###　D. 手机信号

手机信号

set 暴力维护三元组，细节挺多的，因为保证新建的区间内是空的，所以每次插入最多影响两个区间，所以复杂度正确