傳送門

http://poj.org/PRoblem?id=1741

題目大意

給出一顆n$n$ 個節點，n?1$n-1$ 條邊的樹，詢問兩點(u,v)$(u,v)$ 滿足起簡單路徑的長度小于等于k$k$ 的方案數，k$k$ 為給定常數。

我的想法

考慮一顆樹，那么(u,v)$(u,v)$ 有兩種可能：要么過樹根，要么不過樹根x$x$。 考慮點分治，如果過x$x$ 的話直接遞歸就好了；不過x$x$ 呢，我們可以把所有點到x$x$ 的距離d(u,x)$d(u,x)$ 算出來，如果存在兩個點(u,v)$(u,v)$ 滿足dis(u,x)+dis(v,x)≤k$dis(u,x)+dis(v,x)/leq k$ 就滿足條件。但是可能會出現重復的情況，就是這兩個點在x$x$ 的同一顆子樹內，設連接這顆子樹與x$x$ 的邊的另一端點為y$y$，此時他們滿足dis(u,y)+dis(v,y)+2dis(y,x)≤k$dis(u,y)+dis(v,y)+2dis(y,x)/leq k$ ，判一下減掉就好了。 時間復雜度O(nlog2n)$O(nlog^2n)$ 另外，每次找的樹根要盡量是的子樹節點數的最大值最小，也就是找重心，否則如果出現一條鏈那就完了。

代碼