文件名称：link-cut-tree:链接切割树的 C++ 实现
文件大小：2KB
文件格式：ZIP
更新时间：2024-07-15 18:22:27
C++
链接切割树 链接切割树的 C++ 实现。 链接切割树数据结构维护受以下操作约束的节点森林： link(x, y) ：使树以 y 的 xa 子树为根， cut(x) ：删除将 x 连接到其父级的边。 可以使用以下操作查询树： root(x) ：找到包含 x 的树的根， path(x) ：计算根到 x 路径上节点的函数。 所有操作都需要 O(lg n) 分摊时间。 root(x) 可用于测试连通性。 在这个实现中，路径函数计算节点在其树中的深度。 可以使用函数 lca(x, y) 回答动态最低祖先查询。 界面 对于所有 0 <= x, y < n, LinkCut 树(n); /* 具有 n 个节点的新链接切割树 */ 树链接（x，y）； /* 链接 x 和 y */ tree.cut(x); /* 切 x */ 树根（x）； /* 包含 x 的树的根 */ 树深度（x）
【文件预览】：
link-cut-tree-master
----link_cut.cpp(3KB)
----README.md(1KB)