点分治点分治适合处理大规模的树上路径信息问题。实现P3806【模板】点分治1给定一棵有\(n\)个点的树，询问树上距离为\(k\)的点对是否存在。\(n\leq10^4\)考虑简单深搜，对于任意子树，把路径分为经过根节点的路径和不经过根节点的路径。对于不经过根节点的路径，我们递归

点分治以树的重心为根，对子树内的问题分治求解，时间复杂度可以做到\(O(n\logn\timesF(n))\)，其中\(F(n)\)是解决经过根的问题所需要的处理。P3806模版给一棵有边权的树，多次询问树上是否存在距离为\(k\)的点对。\(n\le10^4,m\le100,k\le10^7\)假设现在\(rt\)是根，则