点分治的核心目标是避免重复统计，通过每次选取满足最大连通块大小≤原树大小/2的重心，仅统计经过该重心且长度恰为K的路径，保证每条路径被统计且仅被统计一次。
点分治的核心目标不是“找路径”，而是“避免重复统计”
直接在树上暴力枚举所有点对算距离，复杂度是 O(n²)，K 大或 n 大时根本不可行。点分治的关键在于：每次选一个重心，只统计**经过当前重心**且长度恰好为 K 的路径数量，然后递归处理子树——这样每条合法路径被且仅被统计一次。
注意：重心不等于根，也不是随便选的中心节点；它必须满足「删去后最大连通块大小 ≤ 原树大小 / 2」，这样才能保证递归深度为 O(log n)。用一次 DFS 可以求出重心，别跳过这步，否则退化成链状，复杂度崩到 O(n²)。
统计“经过重心、长度 = K”的路径要分两步走
设当前重心为 rt，先对每个子树 DFS，得到所有节点到 rt 的距离（记作 d[u]）。但不能直接把所有距离丢进一个数组里两两配对——那样会把**同一子树内**的点对也算进来（它们的路径不经过 rt，属于子问题，不该在这层统计）。
- 先遍历每个子树，把该子树中所有
d[u]存入临时容器（如vector），同时更新全局频次表（如unordered_map<int int></int>），但**暂不统计** - 再遍历该子树，对每个距离
d，查全局表中是否有K - d，累加次数；之后才把这批d[u]正式加入全局表 - 最后别忘了单独考虑
rt自身：若K == 0，则(rt, rt)算 1 对（通常题目要求点对无序且不同点，所以K == 0一般不计；但逻辑上要意识到这个边界）
dfs_dist 和 get_centroid 容易写错的三个细节
常见错误不是算法逻辑，而是实现疏漏：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
-
dfs_dist必须传入父节点fa避免回溯到父边，否则会把父方向的距离也计入，导致重复和环 -
get_centroid中计算子树大小时，必须先清空vis[]标记（如果用了全局数组），否则上次递归残留的标记会让 size 计算错误 - 重心找到后，要立刻标记
vis[rt] = true，并在后续所有 DFS 中跳过已标记节点——这是保证子问题互斥的关键，漏掉就全乱了
当 K 很大或负数时，别硬塞哈希表
如果 K 达到 1e9 甚至更大，用 unordered_map 存距离频次可能内存爆炸或哈希冲突严重；而若 K 是负数（虽然距离非负，但题干若允许边权为负就得另说），直接查 K - d 会越界或无效。
更稳妥的做法是：对当前重心下所有有效距离（即 ≥ 0 且 ≤ K）收集后排序，用双指针扫一遍；或者限制距离数组长度，丢弃 > K 的值（因为 d[u] > K 时，K - d[u] if (d > K) continue; 能省不少事。
真正难的不是写对模板，而是想清楚「哪些距离能参与匹配」「哪些已被排除」「哪些还没加入统计池」——这三个状态稍一混淆，答案就差几倍。
