Loj2537 「PKUWC2018」Minimax （线段树合并维护dp）

分类: 文章 • 2025-05-08 11:10:16

分析

设 $f[i][j]$ 表示节点i取j的概率，你会发现只有叶子节点j的祖先有这个值。
然后观察一下他的dp式子，发现可以在线段树合并的时候维护。
然后就可以nlogn了。