HOJ::Problem : 113 - 計步器

http://hoj.twbbs.org.tw/judge/problem/view/113
樹分治。

樹分治，本來覺得很難，實作一遍之後感覺還可以........。
基本上要先找樹重心(也就是一個點當根的話，所有子樹中點最多的子樹點最少的情況)，這是用來優化樹分治的，不然最悲劇的情況會回到O(N^2)。
我一開始重心找爛了.....，樹重心是指子樹中點最多的數量和剩下的點(就是父節點以上的點)一樣多(或差不多一樣)的狀況。(我寫成子樹點的總和......)
這題的重點，先從一點開始(最好是重心)，對每顆子樹做DFS，DFS時計算到根的距離%m，並算出這個數字減m的值是多少，去set裡用lower_bound找最接近的(加上他剩下%m才會最大)，更新最大值，要注意第一顆子樹DFS時set裡沒東西，所以要先丟一個0進去。做完一顆子樹後，將剛剛那些距離全丟到set裡，繼續第二..第三......顆子樹，全做完後，把set丟掉，把函式遞迴處理所有的子樹，對子樹做一模一樣的事(小心不要跑回這次的根)，全做完後，就得到答案了。
一開始TLE，所以我捨棄STD::set改用vector，每次都push到vector裡，但是lower_bound時只找原本傳下去時的範圍，要找下一顆子樹時，更改範圍並排序，這樣可以節省set跟vector合併的時間，而且set insert要O( log n)，這樣結果比較快。