可並堆/左偏樹

bzoj – 2809 dispatching 【可並堆】

傳送門 題目大意: 有一顆樹, 樹上每個點都有兩個屬性值, 一個是領導能力, 和薪水. 現在有一個預算m , 你要在某一顆子樹內選擇一些帶你, 價值為這顆子樹的根節點的領導能力*可僱傭的點的數量, 問最大價值為多少. 思路: 對於每個點維護最大堆和當前堆的和, 然後每次合併完兩個堆後判斷, 如果當前 […]

bzoj – 4003 城池攻佔 【可並堆 lazy標記】 好題!!!

傳送門 題目大意: 小銘銘最近獲得了一副新的桌遊,遊戲中需要用 m 個騎士攻佔 n 個城池。 這 n 個城池用 1 到 n 的整數表示。除 1 號城池外,城池 i 會受到另一座城池 fi 的管轄, 其中 fi < i。也就是說,所有城池構成了一棵有根樹。這 m 個騎士用 1 到 m 的整數表示 […]