BZOJ 3091 城市旅行


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

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


序列版本

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3091 城市旅行


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,