給你一棵樹,求出樹的 重心。

關於重心,題目有定義。

一個點的權值 = max{拔掉那個點後形成的多棵樹中分別的節點數}。

而重心就是權值 最小 的那些點。

用 樹DP 紀錄各節點的 孩子 數。

然後分別枚舉每個 節點,計算其 權值 後 判斷是否更新答案。

我的code

http://snipt.org/zfiJ2

p.s: TLE 一次是因為 無向圖 有 2*m 條邊,真的要記得開到 2*m= =。

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • c2251393
  • 寫完這個你就可以去電樹分治了<(_ _)>