rprp

数据结构

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 数据结构（共3篇）

Luogu P4116 【Qtree3】

我寻思这题为什么LCT题解这么少啊... 这个题目连换根都不要的话LCT岂不是不用维护翻转操作了嘛？然后pushdown,makeroot等等函数都不要写了然后50行就完事了？？？ #include <cstdio> #define R register const int MAX...

Link-Cut-Tree

2020-04-30

0 349

Luogu P3703 [SDOI2017]树点涂色

Luogu P3703 [SDOI2017]树点涂色用LCT中每一个Splay维护颜色相同的点集，则从一个点到根节点的轻边的条数就是这个点的到根的权值。至于路径查询的搞个差分就好，用树剖实现。至于为什么可以直接这样查，是因为LCT里面涉及子树的权值变化只有access函数。在splay中的子树的...

树链剖分 Link-Cut-Tree

2020-05-13

0 395

LCT板子

#define ls(x) ch[x][0] #define rs(x) ch[x][1] int fa[N], ch[N][2], sum[N], val[N], rev[N]; inline void update(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)...

Link-Cut-Tree

2020-06-16

0 354