(詳見 209968 總覽,此處補充核心代碼結構)
關鍵:fa[] 父節點,dist[] 到父節點的相對深度(奇偶性決定同向/反向)。
刪除操作用 id[] 映射新節點,舊位置保留佔位。
值離散化後,記錄每個值的位置列表 pos[val]。
對每個值,雙指針 l,r 維護窗口內需刪除數 ≤ k,最大化 r-l+1。
時間 O(n log n)。
同 ZOJ 3791,dp[step][diff] 記憶化搜尋,預處理 C[n][m]。
邊權 c' = c*(E+1)+1,Dinic 最大流。
流值 flow,最小花費 flow/(E+1),最少邊數 flow%(E+1)。
直接輸出 1。
正向:起點→各點最大剩餘油量 f[i](經加油站置滿)。
反向:終點→各點最短距離 dis[i](經加油站距離歸零)。
枚舉賣油站 i,利潤 (f[i]-dis[i])*price[i] 取最大。
若 f[n]==-1 輸出 -1。
Tarjan 求強連通分量,縮點得 DAG,點權 = 原 SCC 大小。
拓撲序 DP:dp[v] = max(dp[u]+w[v]),答案為 max(dp)。
代碼見 209984。