POJ 1741-TREE

樓教主的男人八題其中一題!!!!!
是一題樹分治（據說是樹分治中的最簡單題）
但對我來說還是極難阿～～～～寫了好久

來說說什麼是樹分治好了
平常碰到的分治題，都是把它切切切切切切切
變得小小軟軟，就可以快速的解決（最差情況是切一次變兩塊）
樹分治也是一樣的，重點在於你要切的好
所以就要選擇切那棵樹的重心，這樣剩下的子樹會長得最平均
也就不會因為人品過低，出現很糟糕的情況了（拔了一個點，仍然剩下一棵樹）
而重心是啥勒？就是『把一個點拔掉後，讓剩下的最大的子樹，節點數最小的那個點』
這樣就可以較為平均的分成一些更小的樹，而使一切變得更簡單～

有了樹分治的概念後，就可以快樂的進入這題了
首先要先想想為什麼會用到分治的概念？
如果樹長得一副星狀樣，重心連出去的所有子樹都只有一個節點，
就可以 O(n) 快速求出（先dfs求距離，然後使用爬行法）
但重點就是他不是星狀樣阿！怎麼辦勒？？？
首先，先假設他是星狀樣，求一次答案，這個答案當然是錯的
因為他少算了『一些』子樹自己跟自己的配對（不然我就不用再這編寫解題報告了XP）
所以我的分治就是再去算一下子樹中的配對然後把它加回來
但這樣還是錯的，因為他只有少算『一些』配對（不是全部都少算）
所以要再把那些多算了的扣掉。由於有點複雜，下面會重寫一次流程

任務：尋找一棵樹中的配對數量
1. 找出重心
2. 假裝是個星狀圖，找出配對數量
3. for 所有的子樹
    1) 加上子樹的配對數量
    2) 把原本就算過的數量扣掉

有點麻煩，但是這樣就AC了XD

http://codepad.org/id4GK8qM