mshd.net
当前位置:首页 >> tArjAn lCA >>

tArjAn lCA

每深搜到一个节点,都把与这个节点相关的查询都处理掉了(包含有当前节点的查询),并不是所有的Q个查询 所以总和是Q而不是每个节点都是Q

最近公共祖先(Least Common Ancestors)对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点。这里...

倍增法:nlogn预处理,logn查询 树链剖分:O(n)预处理,O(logn)查询(常数和码量较大) Tarjan离线算法O(n+q)一次性求出q个询问

网站首页 | 网站地图
All rights reserved Powered by www.mshd.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com