网站首页
编程语言
数据库
系统相关
其他分享
编程问答
stpos
2024-11-11
虚树
建立虚树先把关键点按\(dfn\)升序排序,单调栈维护树上一条链(\(dfn\)单增),初始为根节点\(1\)逐个考虑关键点\(x\):设\(lca=LCA(x,st[top])\),分类讨论:\(\hspace{0.5cm}\)①若\(lca=st[top]\),表明\(x\)和\(st[]\)同一条链上,直接入栈;\(\hspace{0.5cm}\)②若\(lca\not=st[top]\),则\(l