Codeforces 980F Cactus to Tree 仙人掌 Tarjan 樹形dp 單調隊列

​​題目傳送門 - CF980F​​題意

　　給定一個 $n$ 個節點 $m$ 條長為 $1$ 的邊的每個點最多隻屬于一個環的仙人掌。

　　現在請你通過删邊把仙人掌轉化成樹。

　　對于每一個點，輸出在所有不同的删邊方案中，  距離該點最遠的點與他之間的距離值 的最小值。

　　$n\leq 5\times 10^5$

題解

　　首先，我們跑一跑 Tarjan ，找出每一個雙聯通分量。

　　然後我們把每一個雙聯通分量裡面的點按照順序存在 vector 裡面。

　　我們稱每一個環中連向環的父親環的節點為該環的 環根 。

　　然後我們考慮從下網上跑一跑 樹形DP ，處理出以每一個點為根的子仙人掌中所有不同的删邊方式中最遠點距離的最小值。

　　這次 DP 結束後，我們記第 $i$ 個節點的結果為 $Deep_i$ 。其中，對于任意環根 $i$，特殊地， $Deep_i$ 的涉及範圍為以目前環為根的子仙人掌。

　　為了後面的友善，對于任意環根我們還需要記錄兩個值 ： $spDeep_i,\ \ usDeep_i$ 。

　　具體含義見下圖：

　　

　　對于環根 $x$ ，顯然有 $Deep_x=\max(spDeep_x,usDeep_x)$，要求 $spDeep_x$ 可以通過預處理前字尾 $\max$，然後枚舉該環的斷邊來得到。

　　下一步，我們需要處理一個 $Far_i$。

　　對于環根： $Far_i$ 表示下一步從該環根上行，最優情況下的最遠距離。

　　對于普通的點： $Far_i$ 表示下一步從該點向同環的點走，最優情況下的最遠距離。

　　隻要處理出這個東西，則第 $i$ 個節點的答案就是 $\max(Far_i,Deep_i)$ 了。

　　我們考慮一下那些會對 $Far_i$ 有貢獻的節點。

　　第一種，目前點不是環根，則向同環的節點走會有貢獻。

　　第二種，目前點是環根，向同環的點和向父親走都會有貢獻。注意，這個向父親走的貢獻有兩種，一種是由父親的其他子節點來的，一種是由父親的同環節點來的(父親的 $Far$ )。

　　如果是環根，那麼我們特殊處理即可。

　　現在考慮處理非環根的 $Far$ 。

　　通過證(感性)明(了解)，我們可以發現，對于目前環，當起始點在被順時針周遊的時候，最優方案下删掉的邊也是 大緻 順時針移動的。

　　我們可以維護目前點兩個方向的節點最大貢獻值盡量平衡來擷取最優解。

　　于是我們可以用兩個單調隊列來實作。這一部分是關鍵。需要把環鋪成三倍長度，并加上特定的權值。

　　這裡具體不展開描述了，可以參見代碼。

　　我由于彈出單調隊列 QR 的時候少彈了一個位置， wa on test 18，找了5個多小時QAQ 。

代碼

再放一份打滿調試語句的代碼：