bzoj 1023 [SHOI2008]cactus仙人掌圖

LINK：cactus仙人掌圖

求仙人掌圖的直徑。

每條邊最多屬于一個環中 那麼每條邊要麼是割邊要麼是環中邊。

求直徑,考慮直徑由某個點發出 套用樹形dp求直徑。f[x]表示從x出發的最長鍊。

發現帶環很難搞 對于某個環 我們能夠找到其由于點雙的存在如果發現沒有割點的存在那麼一定有環了(自環也算.

考慮在求點雙的時候把環搞出來。

對于環 此時我們讓每個點都得到環上的貢獻 且此時更新全局答案 也同時更新f[x]的答案。

可以發現答案所在這樣可以dp出來。

對于環上的貢獻破環成鍊後 采用單調隊列優化轉移即可。

最後還是覺得這個做法的正确性沒有很好的說明。

考慮直徑所在 必然由兩個點之間的距離加兩個點所能延伸的不重合的最長距離得到。

在dp的過程中 可以保證f[x] f[tn]的不重合性。

考慮在樹上時我們都是直接合并的 考慮出現了環 且環和環之間沒有重邊 這意味着f[x] f[tn]也存在不重合性。

考慮在環上怎麼辦 兒子仍然是兒子 但是整個環可能可以作為答案 是以我們任選換上兩點進行更新答案。

外部的不用管。是以可以發現這樣做是正确的。