没有合适的资源?快使用搜索试试~ 我知道了~
link-cut-tree:链接切割树的 C++ 实现
共2个文件
md:1个
cpp:1个
需积分: 5 0 下载量 159 浏览量
2021-06-26
00:35:47
上传
评论
收藏 2KB ZIP 举报
温馨提示
链接切割树 链接切割树的 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.zip (2个子文件)
link-cut-tree-master
link_cut.cpp 3KB
README.md 1KB
共 2 条
- 1
资源评论
EngleSEN
- 粉丝: 47
- 资源: 4502
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功