zhltao

分类

未归档(3) 游记(1) 笔记(7) 题解(9)

/ 注册

全部文章（共1篇）

长链剖分求 k 级祖先

前置知识大概学过重链剖分吧。重链剖分是重儿子，即 sz 最大的儿子，这个剖分是指长儿子，即 dep 最大的儿子。这样子可以把树剖成一条一条链。比如下面这个图绿色的部分就是长链。一个节点到它所在的长链的链底部的路径，为从这个节点到它子树每个子树所有节点的路径中，最长的一条。一个节点到根...

树上倍增树链剖分

2020-09-06

0 762