P5298 [PKUWC2018] Minimax 解説：セグメント木マージによる木DP最適化
問題の分析
この問題は、セグメント木のマージ操作を用いて木構造上の動的計画法を最適化する手法が鍵となります。
まず、値の範囲が最大で10^9まで及ぶため、離散化（座標圧縮）が必要です。各値の出現確率を管理する必要があるため、基本的な木DPを考えます。
動的計画法の設計
dp[v][j] を頂点vにおいて、j番目に小さい値が出現する確率と定義します。遷移は以下の3 ...
6月28日 02:04 投稿