Mato is No.1

（從NOI以后一直在各網站上做水題……誰叫我這么弱做不動難題呢……）
（最近實在感覺到弱得令人吃驚……這樣下去還混什么集訓隊啊……于是只好去挑難題了……中間對某些知識點有一些見解……就總結在這里了囧……）

（最近見到了比較多的樹分治的題目，因此第0個總結的就是樹分治了……）

相關論文

樹分治用于解決有關路徑的問題。
樹分治分為點分治和邊分治（其實還有一種叫“鏈分治”，是樹的路徑剖分思想的更高級的體現，一般鏈分治的題目都可以用路徑剖分解決）。點分治就是每次找到重心，然后把重心去掉，對分成的每兩棵樹之間分別統計路徑信息（以重心的每個相鄰點為根，遍歷整棵子樹即可得到這個根到每個結點的統計信息），就可以知道包含這個重心的所有路徑的信息，然后對于剩下的路徑就是在子樹里面進行同樣的操作了，直到只剩一個點為止（注意這一個點所構成的路徑有時也要處理一下）。邊分治就是每次找到一條邊，使得刪掉這條邊后分成的兩棵子樹大小盡可能平均，然后以刪掉的邊的兩端點為根，分別統計根到兩棵樹中的每個結點的路徑信息，最后合并算路徑，即可得到包含這條邊的所有路徑的信息，剩下的路徑在兩棵樹中遞歸處理。

點分治和邊分治是可以通用的，不管樹上的信息記錄在結點上還是邊上。這時一個很囧的問題就出現了：這兩種分治到底哪個好？這也是本總結討論的重點。
有關“哪個好”的問題顯然要從三種復雜度上考慮。由于點分治和邊分治的空間復雜度均為O(N)，因此討論空間復雜度木有意義。所以需要比較的就是時間復雜度和編程復雜度了。
先說時間復雜度。點分治每次找到重心后，需要將重心刪掉然后分成很多棵子樹，對每兩棵子樹之間都要統計一下。如果操作是可反的（比如計數問題：統計某種路徑的條數），可以通過先將所有子樹合在一起統計，再減去兩端點處在相同子樹內的路徑，但是，如果操作不可反（比如找“最優路徑”），就不能這樣做了，只能枚舉所有的子樹對。顯然，如果有S棵子樹，則有O(S²)個子樹對，最壞情況下（星形的樹），S=N-1，此時一一枚舉子樹對必然會導致總時間復雜度升到O(N²)以上。當然這是有解決辦法的，可以從小到大枚舉子樹，每處理完一棵子樹就將其和前面的合并，此時算法效率取決于合并的方法。如果使用歸并法（大小為A的和大小為B的合并次數為A+B），對于星形樹的合并總次數仍然為O(N²)，如果能保證大小為A的和大小為B的合并次數為min{A, B}，則可以保證合并總次數在O(N)以內，從而可以保證總時間復雜度為O(NlogN)。邊分治由于分成的永遠是兩棵子樹，所以在處理子樹之間的關系上能夠保證O(N)，問題是它并不能保證每次分成的兩棵子樹大小非常平均，在最壞情況下（星形的樹），不管刪哪條邊分成的兩棵子樹大小都是一個1一個(N-1)，這樣就會使總的時間復雜度上升為O(N²)。

從以上的討論中可以看出，點分治和邊分治最怕的都是星形的樹，也就是那種某個點的度數特別大的樹。相關論文中提到一種辦法通過加無用點的方式將其轉化為二叉樹，從而解決這個問題。這樣一來，點分治和邊分治的時間復雜度都可以保證了。接下來是編程復雜度的問題：點分治需要找重心（三次DFS或BFS），刪掉重心（需要刪點），且分成最多三棵樹，需要處理三對關系，代碼量肯定大一些，而邊分治只需要算出子樹大小后就可以找到最優邊，并且分成的是兩棵樹，更重要的是，在有根樹上刪掉一條邊后，分成的兩棵樹中有一棵已是有根樹，另一棵可以通過扭根的方式將其轉化為有根樹，由于二叉樹扭根是很方便的，所以就不需要每次重新建樹，代碼量較小。綜合以上因素，邊分治更好些。

另外，其實那種加無用點轉化為二叉樹的方式是有問題的，因為它改變了路徑的意義，可能導致一條路徑由于LCA是無用點而在統計時出現錯誤（明明是跨越了重心或最優邊的路徑被當成木有跨越的），但是……這個問題有一種很簡單的解決辦法，想知道是什么……AC了ALOEXT再告訴你……

相關題目：
<1> (2013年候選隊互測•a142857a) 樹
邊分治，每次找到所有點到根路徑的XOR和，以及特殊點的個數，按照特殊點個數排序后有序插入Trie，查找即可。
代碼：
<2> (VK Cup 2012 R1-D) Distance in Tree
邊分治，很容易實現，不說了。
代碼：不顯示。