点分治
处理树上路径有关问题。以一个点 \(x\) 为根，经过 \(x\) 的路径可以在 \(x\) 处拆开。原先是 \(u\rightarrow x\rightarrow v\)，拆成 \(u\rightarrow x,x\rightarrow v\)，快速处理这个部分再合并就可以得到所有经过 \(x\) 的路径了。
每次枚举一个 \(x\) 处理路径，将 \(x\) 删去，之后递归若干颗子树。每一次选择子树的重心。这样每一次选择重心后每一颗子树大小不超过原来树的一半，那么递归深度限制在 \(\log\) 级别。
点分树
我们将每一次递归的重心连边得到一颗新树。
P6626
给出 \(x\)，求与 \(x\) 距离为 \(k\) 的数量。
点分治做法
离线，枚举分治中心 \(x\)，求出每个点到 \(x\) 的距离，再去处理子树中的询问。对于子树中询问有一个子树 \(y\)，\(y\) 子树有到 \(x\) 的询问点 \((u,k)\)。那我们要求出 \(y\) 子树内每个点到 \(x\) 的距离。我们要求从 \(u\) 出发，距离为 \(k\) 的点的数量，即 \(u\rightarrow x\rightarrow ?\)。容斥。
点分树（在线）
对于点分树上的点 \(x\)，记录以 \(x\) 为分治中心时，距离桶，与它的父亲为分治中心时 \(x\) 的桶。与原树上到每个点分树祖先的距离。
那么考虑类似上述做法容斥。