PKU2378-Tree Cutting

題目：http://poj.org/problem?id=2378
題如其名，給一個有N(10000)個節點的無根樹，
問有哪些節點被拔掉以後，殘餘的各分塊節點數皆不超過N的一半？
(換句話說，這樣的點如果當樹根、所有子樹的總點數<=N/2)


程式碼：http://codepad.org/EhCfH6qT
入門級樹形DP，USACO月賽好題真不少…(望USACO Training)
定義dfs(n,p)表示，如果從p當樹根的角度來看、以節點n為首的子樹共有幾個節點？
所以一開始以虛擬結點0為樹根、任意取一個起點dfs(1,0)

然而這樣的dfs樹是有高低分層的、怎麼樣每一輪都能完整判讀「節點n是根」的情形呢
答案就是把「層次上的子樹」和「父節點」分開討論

好比說範例測資(畫個圖吧)我們從1起點，現在走到了dfs(3,2)
節點3實際有3個分支：2,4,8
我們對4,8遞回dfs(4,3)、dfs(8,3)，就能知道分支4,8的子樹節點數(判斷是否合題設)
於是發現一個巧妙的點，在dfs tree上父節點2的狀態、也隨著4,8遞回完就呼之欲出了

以2當子樹=N-(以4當子樹)-(以8當子樹)

於是本題得解

文末附上一道類似問題：找關鍵人物(97全國賽)
http://zerojudge.tw/ShowProblem?problemid=b218