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