UOJ 87. mx 的仙人掌

參考資料

官方題解
https://blog.bill.moe/uoj87-mxcactus/

題意

給定一個仙人掌,每次從中選取幾個關鍵節點,求它們之間兩兩之間距離的最大值。

題解

對於樹的情況,如果你只會虛樹或者樹分治,對於仙人掌你肯定也只能這麼做了。
—— 官方題解

所以這個題乃會幾種做法,取決於樹的版本的那個問題,你會幾種做法。官方題解 的六、七、八、九,提供了四種思路。這裡先實現第一個演算法 —— 虛仙人掌。

虛樹

先當成樹做,拿個 30 分再說。。。這裡我用 f[] 數組記錄向下的最長距離,然後在更新 f[u] 之前,先用 f[v] 和 f[u] 一起更新一下全局的直徑,這樣就不需要記錄次大值了!

http://uoj.ac/submission/387435

虛仙人掌 (a.k.a. 圓方樹)

首先對這類題目來說,通常的做法,是 dfs 的時候,找到環,然後再環上手工 dp 一次(但其實我總是敲錯,需要依靠底力),把經過環的結果統計到答案,並更新到環上的根節點。
事實上對於 BZOJ 1023. [SHOI2008]cactus仙人掌圖IOI 2008 D2T1 Islands 我們就是這樣做的(分別是 直徑 和 最長鏈,轉移方程幾乎一樣)。

但我們發現並不是總能靠底力凹出來,比如 BZOJ 2125: 最短路,樹上兩點的最短路需要求 lca,仙人掌上怎麼求 lca,似乎需要大量 if-else 判斷 = =!!!
這個題的情況類似,因為在構建虛樹的過程中,我們也需要求 lca。

這個時候我們就需要使用一種 常用的技巧 圓方樹。參見 圓方樹——處理仙人掌的利器

簡單說來,圓方樹就是把環邊都去掉,新建一個 方點 來代替這個環,用環上的根節點連一條邊到她,在從她到每個環上的其他節點連一條邊,形成菊花形狀以拆環為樹(怎麼樣?是不是很像 block-cut tree)。

具體實作的話,先建三個結構體,分表表示 —— 原圖,圓方樹,虛樹。分別記作 G,C,T。求圓方樹的過程,可以類比 tarjan 求雙聯通分量,我這邊是在最深的節點拉回反向邊的時候,把環摳出來的(因而需要取個反)。
這裡連向方點的權值為 0,而從方點連出的邊的權值為左右兩條路徑的長度取 min。

緊接著在 C 上再 dfs 一次,預處理出 dp 和 lca 所需要的信息,為構造虛樹做準備。最後求虛樹的地方,和 之前寫的代碼 唯一的不同,是如果是從方點連出去的邊,需要把這個環上連出去的那個孩子也加到樹中,因為我們需要這些節點來正確處理環上的 DP。

void add_edge(int x, int y) {
if (x > G.n && x != C.fa[0][y]) { // 如果是從方點連出去,並且 y 不是連出去的那個孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
adj[x].PB(z);
x = z;
}
adj[x].PB(y);
}

這個地方也是之前裸凹的時候最麻煩的地方,因為現在有了圓方樹,所以幾行就處理了掉了w。

接下來是下一個容易錯的地方,以樣例來說,在建立虛樹的時候我們會把 2 和 9 所在的這個環也加到虛樹里,而這個環本身的信息有可能會節外生枝,包含一些本不應該被考慮到節點(這裡是 7),所以我們更新答案的時候乾脆只用圓點的信息更新即可(上面 add_edge 里補上的節點並不會影響)。

參見 下圖

最後說一個讓我 wa 成傻逼的地方,就是最後的資源回收。。。因為這種虛樹的題通常我們是不能無腦 memset 的,但是我們剛才構建虛樹的時候,中間又加入了一些新的節點,所以直接 for 循環那個數組的話會錯。。
所以,最好在遍歷樹結束的同時把這些不用的信息都清理掉。。。

http://uoj.ac/submission/387655