【UOJ 67】

題目鏈接：

　　傳送門(mén)

題解：

　　第一眼很懵逼……這什么鬼。

　　思考什么點(diǎn)復(fù)合條件……（o(>﹏<)o

　　1.樹(shù)，也就是說(shuō)還剩n-2條邊，等價(jià)于要?jiǎng)h去一個(gè)度數(shù)為m-n+2的點(diǎn)。

　　2.還是樹(shù)，也就是說(shuō)聯(lián)通圖，等價(jià)于選取點(diǎn)不能是割點(diǎn)。

　　……想不出來(lái)了。然后？然后就夠了233。證明什么的，顯然……（當(dāng)時(shí)智障的我

代碼：

　　

View Code

?

BZOJ 1123BLO

題目鏈接：

　　傳送

題解：

　　此題唯一要求的大概就是某個(gè)割點(diǎn)下各個(gè)DFS樹(shù)上子節(jié)點(diǎn)的大小。

　　思考……

　　DFS樹(shù)……

　　1.點(diǎn)雙走的可以看做一個(gè)有“回邊”的樹(shù)

　　2.割點(diǎn)的每個(gè)聯(lián)通塊是獨(dú)立的，也就可以看做其子樹(shù)

　　3.除割點(diǎn)以外點(diǎn)答案都是$2n-2$。

　　思考完畢。在求割點(diǎn)的同時(shí)，記錄一個(gè)$size$表示DFS樹(shù)上某節(jié)點(diǎn)子樹(shù)大小。對(duì)于割點(diǎn)，我們只要再記錄一個(gè)$num$，來(lái)統(tǒng)計(jì)各個(gè)聯(lián)通塊大小，亂搞一下就好了。

代碼：

View Code

?

?

所以說(shuō)，圖論還是多畫(huà)圖嘛……雙聯(lián)通也沒(méi)什么特殊的233不要怕233

轉(zhuǎn)載于:https://www.cnblogs.com/Troywar/p/7688973.html

總結(jié)

以上是生活随笔為你收集整理的【UOJ】67 新年的毒瘤 【BZOJ】1123 BLO的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。