树分治-点分治

看到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)\)

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

(更多…)




莫比乌斯反演整理

UPD:我就是个菜鸡QAQ写的这些东西哎……太弱的时候什么都敢乱写……神犇看到就当开笑话嘛QAQ……求不喷

莫比乌斯反演通常是利用莫比乌斯函数来简化一类逆向求函数的问题。
设\(F(n)\)与\(f(n)\)是定义在自然数集合上的两个数论函数,并且满足条件$$
F(n) = \sum_{d|n}f(d)
$$或者$$
F(n) = \sum_{n|d}f(d)
$$已知的\(F(n)\),求\(f(n)\)的表达式。

观察\(F(n)\)式:\(F(n)\)被\(F(xn)(x > 1)\)所包含。所以,只需类似解多元一次方程一样,通过抵消系数的方法(容斥)就可以逐个求出\(f(n)\)。
但是这样太慢了!于是我们想加速这个过程。
我们希望,存在一个函数,使得\(F(n)\)可以直接被表示出来。 (更多…)


ˆ Back To Top