BZOJ 3091 城市旅行

发布于 2017-11-22  165 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3091

题意:维护动态树,支持链上加权,询问链上随机选两个点路径权值和的期望。 


序列版本

但是由于 link,cut 操作会改变节点的位置,所以不能简单套用序列版本。

分母是显然的,考虑分子,可以通过左右节点合并得到,具体合并过程可以看 popoqqq 大爷博客(逃

 


一个非常弱的准退役OIER