树分治-点分治

看到akb在冬令营就切了好多点分治就好慌啊qaq,然后机房里也有一堆人写点分治qaq,然后我就被点分治虐了啊qaq……

树上的点分治是一种针对树上路径统计的问题的算法,通过找到重心使得子问题规模快速下降,再将所有子问题答案合并起来,通常能够将\(O(n ^ 2)\)规模的问题优化为\(O(n \log n)\)或者\(O(n \log ^ 2 n)\)。

先看一道题:
给定一颗\(n \leq 10 ^ 5\)个节点的带权无根树,设\((i, j)\)之间的简单路径边数为\(dis(i, j)\),求所有满足\(dis(i, j) \leq K\)且\(i \lt j\)的数对\((i, j)\)的数量。(CWOJ1201

暴力做法显然,从每个节点开始dfs (bfs是等价的,后文dfs均可以用bfs解决),记录答案即可。时间复杂度为\(O(n ^ 2)\)

但是这样太慢了!我们想要更快的做法。

(更多…)





ˆ Back To Top