Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共4篇）

树链剖分详解

预备知识：线段树，DFS序 DFS序 DFS序，字面意思，就是DFS到的顺序我们只需要在搜到节点的时候记录一下就可以了比如这样可能是一个树的DFS序那知道了DFS序又有什么用呢我们可以发现一颗子树在DFS序上是连续的一段那么它就有了一个区间的性质，每个节点对应一...

数据结构树链剖分

2018-12-27

0 524

[JLOI2014]松鼠的新家 (树剖)

题目 P3258 [JLOI2014]松鼠的新家解析非常裸的一道树剖题链上修改+单点查询的板子记录一下所经过的点\(now[i]\)，每次更新\(now[i-1]到now[i]\) 我们链上更新时上一次到的终点，是这一次一次更新的起点，又因为在\(a_n\)处可以不放糖，所以我们...

树链剖分

2019-05-03

0 514

SP375 QTREE - Query on a tree (树剖)

题目 SP375 QTREE - Query on a tree 解析也就是个蓝题，因为比较长树剖裸题（基本上），单点修改，链上查询。顺便来说一下链上操作时如何将边上的操作转化为点上的操作：可以看到这个题然我们对边进行操作，我们的树剖是对节点进行操作的，所以我们考虑把边权变为点权。 ...

树链剖分数据结构

2019-05-04

0 541

BZOJ1832: [AHOI2008]聚会(LCA)

题目： 1832: [AHOI2008]聚会解析：偶尔做做水题挺爽的两两之间先求出LCA，发现至少有两个LCA是相同的，这个重复LCA也是深度最浅的那个，那我们就选择那个不重复的LCA，因为若选这个重复的LCA的话，这个重复的LCA到另一个LCA的路径会走两遍，反之只会走一遍三点间的距...

LCA 树链剖分

2019-08-19

0 484