zcmimi's blog

arrow_backlct共22篇文章

avatar
zc
2020-04-23 14:02:00
查看原题

点击跳转

线段树分治+LCT

一个非常暴力的思路

FBI WARNING: 极有可能因为常数巨大而超时

把询问(修改)时间看成序列,每条边在这个序列上的一段区间出现

avatar
zc
2020-04-20 17:17:00
查看原题

点击跳转

要转化为加边,之后用并查集维护是否连通就可以了(带权维护连通块大小,为n的时候说明全部连通)

每条边都在特定的时间段中出现

由于加边完还要删掉这里使用按秩合并

avatar
zc
2020-04-19 00:28:00
查看原题

点击跳转

定义

二分图又称作二部图,是图论中的一种特殊模型。

G=(V,E)是一个无向图,

如果顶点V可分割为两个互不相交的子集(A,B),

并且图中的每条边i\leftrightarrow j所关联的两个顶点ij分别属于这两个不同的顶点集(i \in A,j \in B),

则称图G为一个二分图。

简而言之,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

判断

区别二分图,关键是看点集是否能分成两个独立的点集。

无向图G为二分图的充分必要条件是: G至少有两个顶点,且其所有回路的长度均为偶数。

证明:

必要性:

G=<V,E>为一个简单无向图,G为二分图,那么可以将V分为V_1,V_2

CG中长度为l的圈,C=(v_1,v_2,...v_{l-1},v_l,v_1)

那么v_1\in V_1,v_2\in V_2,v_3\in V_1 ,\cdots,v_l \in V_2

也就是:

v_1,v_3,v_5,\cdots v_l-1 \in V_1 \\ v_2,v_4,v_6,\cdots v_l \in V_2

所以l必定为偶数

充分性:

设无向图G中每个圈的长度都是偶数,并且假定G为连通图

定义V的两个子集V_1,V_2:

任取v\in V,

V_1=\left\{v|dist(v_i,v) \mod 2 = 0\right\}

V_2=\left\{v|dist(v_i,v) \mod 2 = 1\right\}

V_1的节点间无边连接,

假若不然,设有边v_i\leftrightarrow v_j\in Ev_i,v_j\in V_1,那么vv_i以及vv_j的长> 度都是偶数,

那么vv_iv_jv这个圈的长度为奇数,与给定条件矛盾,所以边v_i\leftrightarrow v_j不存在

同理可证V_2的节点间无边连接

回归正题,我们要判断是否是二分图,只需要判断图里是否存在奇环就可以了

解法一

link-cut tree

考虑到每条边最后都是要删掉的,那么当构成环时,我们就可以将该环中最早要被删掉的边给删去,因为这样一来不会影响连通性,二来又可以化环为链。

添加一条边的时候,若两端未连通,直接连边即可

若两端已经连通,这时一定会形成一个环,为了维护LCT,连接两端时,我们需要把环上消失时刻最早的边给删去,如果是奇环则把这条边加入集合

删边时如果是LCT上的边则断开,在集合中则将其从集合中删除

查询时若集合中没有边,则为二分图

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-11 22:16:00
查看原题

点击跳转

LCT维护重心

这里利用了两个重心性质:

  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个距离和,他们的距离和一样。

  2. 把两棵树通过某一点相连得到一颗新的树,新的树的重心必然在连接原来两棵树重心的路径上。

我们需要维护子树的大小

合并的时候连接两棵树,分离出连接原来两棵树重心的路径,在链上搜索出答案

方法类似平衡树的查找

avatar
zc
2020-04-10 20:51:00
查看原题

点击跳转

解法一

化边为点

每个点的父边赋予该点的颜色。我们需要两个LCT,每种对应一个颜色。一条边只有在对应颜色的LCT中才会被连上。

接着可以发现,修改一个点的颜色,只需要在原来颜色对应LCT中断开父边,在新颜色LCT中连接父边,就可以维护同色连通块了

查询的时候只要找到x所在splay的根,右子树大小就是答案(相当于边的数目,根的深度最浅,只有右子树)

注意: 1节点是没有父亲的,不过为了模型的建立,要有父边,于是需要加一个虚点,让1的父亲指向它连边

手动模拟一下应该可以懂

avatar
zc
2020-04-09 20:43:00
查看原题

点击跳转

还是QTREE6的方法

从维护子树大小变成了维护子树最值

avatar
zc
2020-04-07 20:04:00
查看原题

点击跳转

fhqtreap做法

在普通fhqtreap的基础上记录节点的父亲

M x y: 一直向上走就可以找到根,然后合并即可

D x: 求出x的排名,然后按排名分裂即可

Q x y: 求出x,y排名,分裂,得出答案,再合并回去

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求解都可以

这里采用树剖+树状数组

1/3
Search
search