Kruskal重构树需新建虚点并重定向父指针，仅排序边得到的是MST而非重构树；虚点权为边权，父子关系由并查集合并顺序决定，叶子为原图节点（1~n），内部节点为虚点（n+1~2n−1）。
为什么 Kruskal 重构树不能直接用 std::sort 排完边就完事
因为重构树本质是建一棵新树，不是单纯求 MST；原图的边权要变成新树的点权，而父子关系由并查集合并顺序决定。跳过「虚点创建」和「并查集父指针重定向」这两步，得到的只是 MST 的边集，不是重构树结构。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 每轮
union合并两个连通块时，必须新建一个虚点（编号从n+1开始），该点权值 = 当前边权 - 并查集的
parent数组不能只存根，得额外维护tree_parent：虚点的父节点是这次合并后的新根（即新虚点），两个旧根都连向它 - 别复用原图的
find函数返回值当树节点——它返回的是集合代表元，不是重构树上的实际节点编号
怎么给重构树打标记：DFS 序 + 线段树还是倍增 LCA
重构树是二叉树（每个虚点恰好合并两个子树），但不一定是满二叉树；它的核心价值在于：原图中两点路径最大边权 ≤ x，等价于它们在重构树上的 LCA 权值 ≤ x。所以标记/查询通常围绕 LCA 展开。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 如果只做「单次询问两点是否可达（限权）」，不用建任何数据结构，直接倍增跳
lca，比较weight[lca]和阈值即可 - 如果要做「所有满足
weight[u] ≤ x的 u 的子树大小」，就得 DFS 求出进出时间戳，再上线段树或树状数组 - 注意：重构树的叶子节点对应原图的点（编号 1~n），内部节点才是虚点（编号 n+1 ~ 2n−1），初始化线段树时叶子位置要映射对
std::vector<std::pair<int, int>> 存边够不够，要不要上 struct Edge
够，但容易漏信息。Kruskal 重构树需要同时访问边权、端点、以及后续用于构建树的「处理顺序」，用裸 pair 容易在排序后丢掉原始索引或混淆方向。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 定义
struct Edge { int u, v, w, id; };，id不为序号而是为了调试时定位哪条边触发了哪个虚点创建 - 排序用
std::sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a.w ，别手写比较函数漏 const 引用，否则大数组下性能暴跌 - 别把边存在
vector<vector<pair<int, int>>>邻接表里——重构树不需要原图邻接关系，存了纯占内存
重构树建完发现跳 lca 返回 0 或越界，常见原因
基本是节点编号没对齐，或者并查集初始化范围错了。重构树总节点数是 2 * n - 1，但很多人只开了 n + m 大小的数组。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 数组如
fa（并查集）、dep、up（倍增父节点）、w（点权）都要开到2 * n，下标从 1 开始用 - 并查集初始化：前
n个点是原图节点，fa[i] = i；虚点初始不进并查集，只在合并时动态加入 - DFS 建倍增表时，确保只遍历重构树的有效边（即你手动建的
tree_adj），别误扫原图边或未连接的虚点
重构树真正难的不是建树本身，是后续查询时搞混「原图节点」和「虚点」的语义，比如对虚点调用 query_subtree_size 却忘了它没有原图物理意义，或者把 w[lca] 当成路径边数——它永远是某条原边的权值，仅此而已。
