树分治

点分治

例题

[qoj837] Giant Penguin

Portal.

图上做这个有点过于恐怖了，先考虑树上。

求一条从某个关键点出发的路径的贡献，那么点分治，一定是某个关键点走到分治中心，然后再从分治中心走到某个点。

抓一棵生成树出来，那么对于每个分治点最多只有 $k$ 条边跨越它，经过这些边也可以视作跨越的分治点。因此直接对最多 $2k+1$ 个点为起点跑 BFS 即可，代码。