zcmimi's blog

arrow_back树链剖分共22篇文章

avatar
zcmimi
2020-09-03 21:35:00

LG 4719 【模板】"动态 DP"&动态树分治

给定一棵n个点的树,点带点权。

m次操作,每次操作给定x,y,表示修改点x的权值为y

你需要在每次操作之后

avatar
zc
2020-10-27 20:44:01

查看原题

点击跳转

解法一

最小权覆盖集 = 全集 - 最大权独立集

动态dp

只要把强制取点,不取点可以分别把点的权值改为正无穷与负无穷

解法二

倍增/树链剖分+树形dp

每次修改的两个点a,b构成一条链

可以链上连接的子树与链中间的点的结果不受修改影响,只有a,b的转移受影响,需要单独处理

那么我们可以把子树的答案都预处理出来,链中间部分可以用倍增或树链剖分维护

这样只需要处理a,b

f(i,0/1)表示i选/不选,以i为根的子树的最小代价,g(i,0/1)表示整棵树除了以i为根的子树的最小代价,可以通过树形dp求出

F(i,j,0/1,0/1)表示i选/不选,i2^j级祖先选/不选,i子树到ii2^j级祖先子树的最小代价,可以倍增求出

avatar
zc
2020-09-08 17:08:00
查看原题

点击跳转

题意:

给出一棵n个点的树,每次询问给出两对叶子,求这两对叶子产生路径的交点数

解法:

先把一条链上的点都+1,然后查询另一条链的权值和就是答案

也就是链加、链查询

可以直接树剖套线段树/树状数组 \log^2

更优秀的线性做法: 虚树

avatar
zc
2020-04-12 15:41:00
查看原题

点击跳转

1 x表示把点x到根节点的路径上所有的点染上一种没有用过的新颜色

从这里可以看出每种颜色在树上都是一条链的形式存在

可以发现这和LCT很像

那么1操作可以看成access操作,(如何操作先放着

x到根的颜色种数也就是要经过的虚边的条数,设为S_x

xy的路径的权值,可以使用树上差分的形式

也就是转化为S_x + S_y - 2\times S_{lca(x,y)} + 1

3操作也就是求子树最值

我们回过头来看access操作:

  1. 原来的实边变虚,意味着要多走一条虚边,将此链所管辖的区域全部+1

  2. 虚边变实边,意味着要多少一条虚边,将此链所管辖的区域全部-1

注意: LCTsplay的父子关系并不是原树中的父子关系,要找到该splay中深度最小的节点(也就是这条链的顶端再操作)

综上可以用 lct+lca+dfs序+线段树 解决

当然也可以通过树剖模拟access的形式来解决

avatar
zc
2020-04-06 22:06:00
查看原题

点击跳转

LCT动态维护最小生成树

维护链上的最大值和次大值

先找出最小生成树,然后枚举剩下的边,找出相差最小的,得出答案

这题还可以用kruskal生成树+倍增(或树剖)做,常数会小很多

avatar
zc
2020-04-05 22:51:00
查看原题

点击跳转

\sum_{i=l}^r deep[LCA(i,z)]

首先,可以把询问拆成两个部分相减\sum_{i=1}^r deep[LCA(i,z)]-\sum_{i=1}^{l-1} deep[LCA(i,z)]

考虑一种暴力解法: 把1-r到根的路径全部+1,再查询z到根的路径和就是答案

可以发现问题的答案是可以叠加求出的

容易想到排序后离线处理

用树剖或LCT求解都可以

这里采用树剖+树状数组

avatar
zc
2020-03-28 15:20:00
查看原题

点击跳转

树链剖分树套树

这里的树套树使用树状数组动态开点权值线段树实现,要先离散化

我的方法算是有点笨但是好写的方法

avatar
zc
2020-03-23 08:44:00
查看原题

点击跳转

avatar
zc
2020-01-27 18:12:00
查看原题

点击跳转

建完广义圆方树后用树链剖分+线段树维护

修改一个点的时候,考虑到要修改它所在的双连通分量中的点,我们可以在(它的父亲)方点建一个对顶堆来维护最小值

avatar
zc
2020-01-27 09:31:00
查看原题

点击跳转

1/3
Search
search