【文件属性】：
文件名称：link-cut-tree:链接切割树的 C++ 实现
文件大小：2KB
文件格式：ZIP
更新时间：2021-06-26 00:35:47
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)