zhltao

分类

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

/ 注册

全部文章（共2篇）

长链剖分求 k 级祖先

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

树上倍增树链剖分

2020-09-06

0 762

树链剖分笔记

树链剖分学习笔记序听 Singercoder 说树链剖分是码农题，然后我否认（雾）。夜已深，屏幕微凉，数据结构，他说：“A了我，快！”，莫名激动。我有一壶酒，足以慰风尘，还是，我心中好不了的伤疤。正文预备知识： LCA 的思想 vector 或链式前向星的...

树链剖分

2020-04-29

0 369