??
題意:求樹上距離小於等於K的點對有多少個。
思路:這道題很容易想到樹分治,對於當前的根節點來說,任意兩個結點之間要麼過根結點,要麼在一棵子樹中。
那麼我們dfs一次求出所有點到根結點的距離,然後用o(n)的時間判定有多少節點對符合,(判斷方法稍後說)
但是這樣有很多在一顆子樹中的節點對我們會求重復,我們需要減去在一棵子樹中結點對小於等於k的數量,也就是說,我們這一步求的是在不同子樹中距離小於等於k的節點對的個數。
接下來說判定方法,將每個點到根結點的距離排序,用兩個指針指向隊首和隊尾,當結點距離和大於k時,隊尾指針減一
否則更新答案並將隊首指針加一。
這道題還有一個問題樣例相當好,因為假如樹退化成一條鏈時,如果我們以任意結點為根那麼遞歸深度將達到O(n),將會tle
所以每次樹分治時我們都要找到當前樹的重心,並以重心為根繼續分治。
#include
#include
#include
#include
#include
#include
#include
#include