[洛谷P5405][CTS2019]氪金手游

这个题再次说明了我不会容斥。
可以发现边按照树的形态全部同向是傻逼题,如果中间边断开概率互相独立,可以分来开做。所以直接容斥,对于反向边将其用正向边和把边删掉来容斥,然后这个容斥可以直接优化成树形dp,时间复杂度$O(n^2)

Tagged with:

发表评论