抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

传送门 首先,看到区间修改,区间查询就要想到线段树。 把链上面的操作转化到点上面的的操作,我们像这样编号,点编号为1...n1...n1...n,边编号为1...n−11...n-11...n−1 于是修改和查询都对应到了边[l,r−1][l,r-1][l,r−1] 考虑如何算期望值,下面的分母很简单,就是Cr−l+12C_{r-l+1}^2Cr−l+12​,从r−l+1r-l+1r−l...