POJ-1741 Tree
题意：给定一棵树，求多少无序对 \((u, v)\) 满足 \(\text{dist}(u, v) \le k\)。
对于树上的路径进行分类：经过根；不经过根。
第二类路径点可以通过递归子树求出。
对于经过根的路径，可以一遍 dfs 求出每个点到根的距离 \(\text{dis}(u)\)。
问题转化为求 \(\text{dis}(u) + \text{dis}(v) \le k\) 且 \(u, v\) 不在同一棵子树的点对数。
如果没有后面子树的限制，可以简单的排序 + 双指针求出，那么只要把每棵子树多算的减掉即可。
单次复杂度 \(O(n\log n)\)。如果直接递归，复杂度高达 \(O(n^2\log n)\)。
考虑 \(rt\) 选取当前树的重心。
\(rt\) 的每棵子树大小不大于 \(n/2\)，如果存在子树 \(u\) 大于 \(n/2\)，以 \(u\) 为重心不会比 \(rt\) 更劣。
因此每次都选重心，树的大小至少减少一半，最多递归 \(O(\log n)\) 层，每层总结点数 \(O(n)\)。
时间复杂度 \(O(n\log^2 n)\)。
P9678 [ICPC2022 Jinan R] Tree Distance
题意：
标签：rt,log,text,复杂度,分治,棵子,20240806,虚树选,dis From： https://www.cnblogs.com/Luxinze/p/18344945