zcmimi's blog

arrow_backdfs序共6篇文章

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

点击跳转

线段树维护动态直径

考虑设A_x为每个点的深度

答案可以写成这样的形式:

ans=\max_{1\le x<y\le n}\{ A_x + A_y - 2A_{\text{lca}(x,y)} \}

考虑欧拉序

因为边权为正,且欧拉序,那么

ans=\max_{1\le x<z<y\le n}\{ A_x + A_y - 2A_z \}

线段树维护区间内的min,max,sl,sr,s

其中min为区间最小值,max为区间最大值

sl_x=\max_{l<i<j<r} \{ A_i-2A_j \}\\ sr_x=\max_{l<i<j<r} \{ A_j-2A_i \}\\ s_x=\max_{l<i<k<j<r} \{ A_i+A_j-2A_k \}

最终答案就是s_1

修改边权可转化为子树(区间)加

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-01-18 22:40:00
查看原题

点击跳转

dfs序作为下标,深度作为时间轴

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

a是确定的,考虑b的情况:

  1. a的祖先

    可以作为b的点的数量是\min(d_x,k)(d_xx的深度),

    a的子树中除a外其他点都可以作为c

    总方案数为\min(d_x,k)\times(siz_x-1)

  2. a子树中

    对于每个b,可以作为c的点的数量为siz_b-1

    我们可以dfs序,记录当前区间中深度为d的数

    然后用主席树(可持久化权值线段树)维护

    这样就可以查询深度\in [d_a+1,d_a+k]的所有'点的子树大小-1'的和

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

解法1

主席树+离散化(深度太大需要离散化)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

线段树解法:

我们记录d_x表示x的深度还有dfs

每个点修改的时候把它的子树都加上val

因为记录了深度,所以d_{x'}如果和d_x同奇偶则加上val,否则减去val

树状数组解法:

1/1
Search
search