点分治初探
点分治是什么： 首先选取一个点将无根树转为有根树，再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处？ 通俗地讲，对任一个点，树的任一条路径要么经过这个点，要么不经过这个点，在这个点的子树里面。这对于树路径的计数等问题能够更容易的解决。 我们先详细介绍如何点分治，再来继续考虑使用。 考虑到我们每一次选择分治中心的时候，我们希望选出的这个根分出的子树的大小都尽量的小，我们可...
点分治是什么： 首先选取一个点将无根树转为有根树，再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处？ 通俗地讲，对任一个点，树的任一条路径要么经过这个点，要么不经过这个点，在这个点的子树里面。这对于树路径的计数等问题能够更容易的解决。 我们先详细介绍如何点分治，再来继续考虑使用。 考虑到我们每一次选择分治中心的时候，我们希望选出的这个根分出的子树的大小都尽量的小，我们可...
首先什么是启发式算法？启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 最简单的就是并查集的按秩合并，每次把小的合并到大的上面，这样找父亲的复杂度就小了很多。 树上启发式合并（dsu on tree）是一种我也不知道为什么叫做这个名字的奇怪算法。 特点是可以在 $O(nlogn)$ 的时间内完成对无修改的子树的统计。 我们考虑这样一个问题：给树上的每一个节点一个颜色，询问每个节点上的...
点双连通分量点双连通图：如果一个无向图上没有割点，那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不经过重复点的路径。 点双连通分量：一个无向图的极大点双连通子图 我们可以使用 Tarjan 求解。 大家肯定都会无向图求割点了，我们其实只需要稍微改一下就可以了。 我们可以发现割点是两个点双的分割点，所以我们用栈来保存按照 $dfn$ 排序的目前还能进入新的点双里的...
前置定义树形图：在一个有向图中，满足存在一个入度为 $0$ 的点，除了该点入读均为 $1$，且该图不存在环，那么称为树形图。 最小树形图：给定有向边权图，求以某点为根的边权和最小的子图，满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边，所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环，所...
UPD：狄利克雷卷积的单位元表示符号建议使用 $\epsilon$。积性函数定义对于一个函数 $f$，若有 $\forall x,y,(x,y)=1,f(xy) = f(x)*f(y)$，则我们称这样的函数为积性函数。 举例：$\phi(x),\mu(i),d_k(n)$（$n$ 的所有正因子 $k$ 次幂和）性质若 $f(x)$ 为积性函数。 设 $n = \Pi p_i^{q_i}$，则...