【BZOJ】2631: tree LCT
【题意】给定n个点的树，每个点初始权值为1，m次操作：1.x到y的点加值，2.断一条边并连一条边，保证仍是树，3.x到y的点乘值，4.x到y的点权值和取模。n,m<=10^5。【算法】Link-Cut Tree【题解】区间加和区间乘标记的处理：【BZOJ】1798: [Ahoi2009]Seq...
[2016北京集训试题14]股神小D-[LCT]
DescriptionSolution将（u,v,l,r）换为(1,u,v,l)和(2,u,v,r)。进行排序（第4个数为第一关键字，第1个数为第二关键字）。用LCT维护联通块的合并和断开。（维护联通块的大小，要维护虚边）答案统计：每当四元组的第一个数为1（这时候合并点u,v所在连通块，反之拆开），...
bzoj 2555 SubString——后缀自动机+LCT
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2555要维护 right 集合的大小。因为 fa 会变，且 fa 构成一棵树，所以考虑用 LCT 来维护……和平常写的 LCT 不太一样。因为要的值是原树上子树里的值，所以没有 makeroot...
Luogu1501 Tree II - LCT
Code #include<cstdio> #include<cstring> #include<algorithm> #define rd read() #define ll long long using namespace std; const int N ...
BZOJ3514：Codechef MARCH14 GERALD07加强版 （LCT+可持久化线段树）
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3514 题目分析：又是一道动态树好题。拿到题面两天之后我都没想出来，结果期末考地理的时候，我做完题无聊在草稿纸上画了画，居然立马知道怎么做了…… 因为我是搜LCT练习题的时候见到这题的，所...
【XSY2528】道路建设 LCT 可持久化线段树
题目描述给你一个\(n\)个点\(m\)条边图，\(q\)个询问，每次问你边权在\([l,r]\)之间的边组成的最小生成树（森林）的边权和。强制在线。\(n,m,q\leq 100000\)题解考虑离线做法。从大到小加边，用LCT维护当前的最小生成树。维护一棵线段树，第\(i\)个位置表示当前的最小...
洛谷P4180 [BJWC2010]次小生成树（最小生成树,LCT,主席树,倍增LCA,倍增,树链剖分）
洛谷题目传送门%%%TPLY巨佬和ysner巨佬%%% 他们的题解思路分析具体思路都在各位巨佬的题解中。这题做法挺多的，我就不对每个都详细讲了，泛泛而谈吧。大多数算法都要用kruskal把最小生成树弄出来，因为要求次小生成树。至于为什么次小一定只在最小的基础上改变了一条边，我也不会严谨的证明。。。。...
王学长的LCT标程
善良的王学长竟然亲自打了一遍QAQ好感动QAQ #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include...
bzoj3669: [Noi2014]魔法森林 lct
记得去年模拟赛的时候好像YY出二分答案枚举a,b的暴力，过了55欸然后看正解，为了将两维变成一维，将a排序，模拟Kruskal的加边过程，同时维护1到n的最大值，加入一条边e(u,v,a,b)时有以下两种情况：1） 若u,v已连通，则找出u->v上最大的b'，若b<b'，则替换之，同时更...
【BZOJ4764】弹飞大爷 LCT
【BZOJ4764】弹飞大爷Description自从WC退役以来，大爷是越来越懒惰了。为了帮助他活动筋骨，也是受到了弹飞绵羊一题的启发，机房的小伙伴们决定齐心合力构造一个下面这样的序列。这个序列共有N项，每项都代表了一个小伙伴的力量值，如果大爷落到了第i个小伙伴的手里，那么第i个小伙伴会把大爷弹到...
【BZOJ】3282: Tree（lct）
http://www.lydsy.com/JudgeOnline/problem.php?id=3282复习了下lct，发现两个问题。。1：一开始我以为splay那里直接全部rot(x)就好了，然后改了好几题lct的题，都过了且速度和原版一样。。然后怀疑了下。。。。。。后来请教神犇，他说这样不行。。...
洛谷P3203 [HNOI2010]弹飞绵羊（LCT,Splay）
洛谷题目传送门关于LCT的问题详见我的LCT总结思路分析首先分析一下题意。对于每个弹力装置，有且仅有一个位置可以弹到。把这样的一种关系可以视作边。然后，每个装置一定会往后弹，这不就代表不存在环么？于是，一个森林的模型被我们建出来了。考虑到有修改弹力值的操作，也就是要断边和连边，于是用LCT维护。思路...
bzoj 2843 极地旅行社（LCT）
【题目链接】http://www.lydsy.com/JudgeOnline/problem.php?id=2843【题意】给定一个森林，要求提供连边，修改点值，查询路径和的操作。【思路】LCT维护sum对于一棵树LCT用splay维护该树的若干重路径，u->fa有三种:一种满足（u->...
bzoj3091 城市旅行 LCT + 区间合并
题目传送门https://lydsy.com/JudgeOnline/problem.php?id=3091题解调了整个晚自习才调出来的问题。乍一看是个 LCT 板子题。再看一眼还是个 LCT 板子题，不过需要考虑两个区间的结果的合并。首先考虑到期望可以转化为每一个区间的权值和。那么对于每一个区间，...
【bzoj3091】城市旅行 LCT区间合并
题目描述输入输出样例输入4 51 3 2 51 21 32 44 2 41 2 42 3 43 1 4 14 1 4样例输出16/36/1题解LCT区间合并前三个操作都是LCT的基本操作，可以LCT水过；重点在于第四个操作。考虑一个长度为n的序列，它的子区间个数为$\sum\limits_{i=1}...
BZOJ 4817 [SDOI2017]树点涂色 (LCT+线段树维护dfs序)
题目大意：略涂色方式明显符合$LCT$里$access$操作的性质，相同颜色的节点在一条深度递增的链上用$LCT$维护一个树上集合就好因为它维护了树上集合，所以它别的啥都干不了了发现树是静态的，可以用$dfs$序搞搞把问题当成树上节点涂色会很麻烦但只有相邻的不同颜色节点才会对答案产生影响所以我们把涂...
[SDOI2017][bzoj4817] 树点涂色 [LCT+线段树]
题面传送门思路$LCT$我们发现，这个1操作，好像非常像$LCT$里面的$Access$啊~那么我们尝试把$Access$操作魔改成本题中的涂色我们令$LCT$中的每一个$splay$链代表同一种颜色的一条链，那么$Access(u)$就相当于把这一段变成同一种颜色注意这个东西能成立，是因为每次涂上...
BZOJ 4817: [Sdoi2017]树点涂色(lct+线段树)
传送门解题思路跟重组病毒这道题很像。只是有了一个询问\(2\)的操作，然后询问\(2\)的答案其实就是\(val[x]+val[y]-2*val[lca(x,y)]+1\)(画图理解)。剩下的操作跟那道题就一样了。代码#include<iostream>#include<cstdi...
【BZOJ4817】【SDOI2017】树点涂色 [LCT][线段树]
树点涂色Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]DescriptionBob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括...
与图论的邂逅04：LCT
本着对数据结构这一块东西的一股兴趣，最近在集训的百忙之中抽空出来学LCT，终于学懂了这个高级玩意儿。前置知识：Splay和树链剖分Splay挺复杂的......这里就先不写，不然篇幅太大。树链剖分倒是可以大致地讲一下。树链剖分什么是树链剖分呢？就是把树给解剖成一条条的链子啦~那就先从最常用的重链剖分...