我在思考樹上的 k 大路徑時找到了一個比較容易做的o(n^2)方法。
（bzoj 3784）
用陣列的中點把陣列切成兩半，計算通過中點的子陣列和，然後分別遞迴
兩邊計算不通過中點的子陣列和，就可以找到第 k 大了。
計算通過中點的子陣列和時，
把左半邊每個元素到中點的子陣列和算出並排序，設為X。
把右半邊每個元素到中點的子陣列和算出並排序，設為Y。
通過中點的子陣列和就可以被表示成 X + Y 了，是一個行與列都排好序的矩陣。
總共會有O(n lg n)個有序矩陣，在裡面找出第 k 大可以在O(n lg^2 n)完成。
（理論上是可以O(n lg n)的，但是應該不實用）
同樣的技巧可以解樹上第 k 大路徑，O(n lg^2 n)或是O(n lg n)。
也可以解樹上 p-center（當然也可以解 path 上的 p-center）
樹上的 p-center 有四種變化：V/V/p, V/E/p, E/V/p, E/E/p。
前三者可以在O(n lg^2 n)內解出，第四個是O(pn lg^2n)
（理論上可以在O(n)和O(n lg^2n)解出）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425652727.A.9F3.html