摘要：
設 \(f_{u,i}\) 表示 \(u\) 接受 \(i\) 的信號，\(u\) 的子樹內的答案。那么可以枚舉 \(u\) 的兒子 \(v\) 接受信號的節點來轉移。注意當 \(v\) 也枚舉到 \(i\) 時要減去重復的 \(k\)。 考慮構造方案，設 \(ans_u\) 表示答案。首先可以求出 閱讀全文
posted @ 2025-02-08 20:55
zhangxy__hp
閱讀(13)
評論(0)
推薦(0)
摘要：
A. Minimum spanning tree for each edge 先建出最小生成樹，對于樹邊答案就是最小生成樹，對于非樹邊就從兩個端點的路徑上刪掉權值最大的即可。 證明：在這個環中，首先強制選了這條邊，然后按照從小到大的順序選邊，則一定不會選到刪掉的那條邊。 Code #include< 閱讀全文
posted @ 2025-02-08 19:14
zhangxy__hp
閱讀(30)
評論(0)
推薦(0)
摘要：
分塊，設塊長為 \(B\)，預處理 \(f_{l,r,x}\) 表示僅考慮 \([1,l]\cup[r,\frac{n}{B}]\) 中的玩具，花 \(x\) 元的最大愉悅度。詢問時向 \(f_{bel_l-1,bel_r+1}\) 中加入 \(l\) 和 \(r\) 所在塊內的玩具即可。\(bel 閱讀全文
posted @ 2025-02-08 10:45
zhangxy__hp
閱讀(12)
評論(0)
推薦(0)
浙公網安備 33010602011771號