CF161D Distance in Tree 題解

Description

​​洛谷傳送門​​

Solution

似乎各種做法都可以過，這裡提供一篇 \(dsu\ on\ tree\) （樹上啟發式合并）的題解。

不會的同學可以看我的部落格 ​​淺談 dsu on tree​​

題目要求我們求出長度為 \(k\) 的路徑有多少條。

那麼我們可以開一個桶 \(cnt_x\)，表示深度為 \(x\) 的點有多少個，統計答案時 \(ans += cnt_{k - dep[x] + 2 * dep[topx]}\) （類似于樹上差分的思想）。

然後修改就比較闆子了，加入一個點的話就 \(cnt_{dep[x]}++\)，删除的話就 \(cnt_{dep[x]}--\)

其他的就沒有什麼了。

具體看代碼吧。

Code

End