轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年3月24日 星期一

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),這樣結果比較快。