zcmimi's blog

arrow_backlct共22篇文章

avatar
zc
2020-04-05 15:11:00
查看原题

点击跳转

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

点击跳转

lct缩点

LG 2542 [AHOI2005]航线规划有点像

缩点的时候顺便和并所有点的信息

avatar
zc
2020-04-03 01:53:00
查看原题

点击跳转

根据套路,用LCT维护子树,信息为最值,每个节点都开一个multiset来记录虚子树信息

思考LCT的定义,每个splay维护的是一条深度单调递增的链(也可以说是实链)

我们定义lm[x],rm[x]分别为每条实链的上端和下端能够到达最近的白点的距离

这样就可以方便地更新信息了

每次求解可以access(x),splay(x),然后x就是树根所在实链的下端,输出rm[x]就可以了

这样不需要换根什么的,也就不需要翻转操作,省去了复杂的pushdown过程

avatar
zc
2020-04-02 09:12:00
查看原题

点击跳转

容易看出x,y切断后,x的子树大小乘上y的子树大小就是答案

LCT维护子树大小即可

avatar
zc
2020-04-01 23:48:00
查看原题

点击跳转

按边权从小到大排序后,依次添加边

问题转化为了:

每次加边的时候,

如果两点为连通,则加边

否则在目前的生成树上找到边权最小的边, 并替换为新边

可以用LCT维护

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

点击跳转

经典的link-cut tree维护连通分量

首先看到这种题我们可以考虑倒序添加

假设每个点代表一个双连通分量,那么两个点之间的关键路径数就是链长-1

可以用LCT+并查集来维护

连接一条边:

  1. 两端在同一个双连通分量中: 什么都不用干

  2. 两端还未连通: 直接link

  3. 两端已经联通: 缩点

    将连接两端的路径提取出来,合并这些点

avatar
zc
2020-03-31 22:37:00
查看原题

点击跳转

avatar
zc
2020-03-29 10:46:00
查看原题

点击跳转

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

点击跳转

还是lct维护最小生成树

先按a变排序,然后b边的处理类似WC2006水管局长

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

点击跳转

lct无脑做

2/3
Search
search