Tethys
Tethys
全部文章
分类
未归档(3)
题解(6)
归档
标签
去牛客网
登录
/
注册
Tethysの小窝
完美撒花✿✿ヽ(°▽°)ノ✿
全部文章
(共2篇)
树链剖分
树链剖分是个好东西呀 我挺喜欢用树剖求\(LCA\)的 因为我不太会打倍增 接下来就稍微说一下树剖的实现 首先我们先引入几个概念: 重儿子:这个点的子树中\(siz\)最大的 轻儿子:子节点中除了重儿子的节点都是轻儿子 重边:与重儿子相连的边 轻边:与轻儿子相连的边 重链:...
树链剖分
2020-07-29
0
398
CF343D Water Tree
题面 这是一道树剖的裸题 (第一次水紫题有点快乐) 这道题其实就是轻重链剖分的操作拿出来罢了 我们看到这道题区间修改,单点查询 不难想到线段树吧 然后我们可以想到轻重链剖分那道题 我们会发现操作\(1\)就是将\(dfn[x]\)~\(dfn[x]+siz[x]-1\)这段区间都赋值为\(1\) 这...
树链剖分
线段树
2020-07-29
0
345