3806

点分治模板题。 点分治适合处理大规模的树上路径信息问题 暴力做法：dfs 每个点 $u$，算出其子树内每个点到 $u$ 的距离，统计经过 $u$ 的所有路径，复杂度 $O(n^2)$。 容易发现，复杂度和子树大小有关。 对于当前子树，我们可以求出其重心，计算经过重心的所有路径，删掉重心，递归每个联通 ......