[模板] 动态树/LCT
简介LCT是一种数据结构, 可以维护树的动态加边, 删边, 维护链上信息(满足结合律), 单次操作时间复杂度 \(O(\log n)\).(不会证)思想类似树链剖分, 因为splay可以换根, 用splay维护重链, splay的中序遍历即为链按深度从小到大遍历的结果.操作注意区分splay和整棵树...
BZOJ_1180_[CROATIAN2009]OTOCI_LCT
BZOJ_1180_[CROATIAN2009]OTOCI_LCTDescription给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无...
沉迷Link-Cut tree无法自拔之：[BZOJ2049]洞穴勘探(蒟蒻的LCT板子)
来自蒟蒻 \(Hero \_of \_Someone\) 的 \(LCT\) 学习笔记最近学了一波 \(LCT\) , 于是怒刷 \(LCT\) 合集......$$学的时候借鉴了 Clove_unique的博客 以及 PoPoQQQ的PPT写得很详细,初学者可以去看看...$$先甩一道板子题......
[Sdoi2017]树点涂色 [lct 线段树]
[Sdoi2017]树点涂色题意：一棵有根树，支持x到根染成新颜色，求x到y颜色数，求x子树里点到根颜色数最大值考场发现这个信息是可减的，但是没想到lct特意设计成lct的形式！如何求颜色数？维护一个点和父亲的颜色是否一样，不一样为1，就是前缀和。考虑相邻的思想和那道“水位线”有点像x到y的答案就是...
CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表
CF1039E Summer Oenothera ExhibitionLG传送门根号分治好题。可以先看我的根号分治总结。题意就是给出长度为\(n\)的区间和\(q\)组询问以及一个\(w\)，每次询问一个\(k\)，问最少把一段给定区间划分几次可以满足每一段划分出的子区间的极差不超过\(w-k\)（...
[bzoj2594][Wc2006]水管局长数据加强版 (lct)
论蒟蒻的自我修养T_T。。和noi2014魔法森林基本一样。。。然而数据范围大得sxbk。。。UPD:这题如果用lct判联通的话可能会被卡到O(mlogm)。。所以最好还是用并查集吧一开始数组开太小re了两发（要开到maxn+maxm），然后又开太大mle一发，然后无限tle。。。把记录类型全改成数...
BZOJ3091: 城市旅行(LCT，数学期望)
DescriptionInputOutputSample Input4 51 3 2 51 21 32 44 2 41 2 42 3 43 1 4 14 1 4Sample Output16/36/1解题思路：大爷比我讲得好到不知道哪里去了PoPoQQQ的博客就是考虑一个点会被经过多少次*多少贡献，...
BZOJ3091城市旅行——LCT区间信息合并
题目描述输入输出样例输入4 51 3 2 51 21 32 44 2 41 2 42 3 43 1 4 14 1 4样例输出16/36/1提示对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=10...
BZOJ2843 极地旅行社 LCT
欢迎访问~原文出处——博客园-zhouzhendong去博客园看该题解题目传送门 - BZOJ2843题意概括有n座岛每座岛上的企鹅数量虽然会有所改变，但是始终在[0, 1000]之间。你的程序需要处理以下三种命令：1."bridge A B"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于...
Cogs 1672. [SPOJ375 QTREE]难存的情缘 LCT,树链剖分,填坑计划
题目：http://cojs.tk/cogs/problem/problem.php?pid=16721672. [SPOJ375 QTREE]难存的情缘★★★☆ 输入文件：qtree.in 输出文件：qtree.out 简单对比时间限制：1 s 内存限制：256 MB【题目描述】一...
3282. Tree【LCT】
Description给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。２：后接两个...
以 BZOJ 2002 为例学习有根树LCT(Link-Cut Tree)
以BZOJ 2002 弹飞绵羊为例学习有根树LCT(Link-Cut Tree)注：本文非常简单，只涉及有根树LCT，对于无根树，LCT还有几个本文没有提到的操作，以后慢慢更新 =v=知识储备[x] splay[x] 树链剖分题意有一棵\(n\)个节点的有根树，动态修改父子关系（保证仍是一棵有根树...
BZOJ 2002 && BZOJ 2409 LCT && BZOJ 3282 初步练习
#include <cstdio> const int Maxn=; inline void Get_Int(int & x) { char ch=getchar(); x=; while (ch<'' || ch>'') ch=getchar();...
lct 模版题 bzoj 2002 2049
很早就有人给我推荐的模版题，然后我最近才刷的(' ' ) 昨天的tree 不知道比他们高到哪里去了，我和他谈笑风生啊！bzoj 2002 弹飞绵羊重点：这道题的cut和link 由于这道题链的特殊性所以不能用提根的方法搞，可以注意到每一次cut位置一定是前面的一个元素，所以access 上去之...
bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊（LCT）
【题目链接】http://www.lydsy.com/JudgeOnline/problem.php?id=2002【题意】给定n个数的序列，i可以跳到i+k[i]，需要能够修改k并可以查询跳出n需要的步数。【思路】把i->i+k看作一条边，则问题抽象为一个森林，越靠后的点离原树的根越近。考虑...
bzoj 2002 : [Hnoi2010]Bounce 弹飞绵羊 （LCT)
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2002题面：2002: [Hnoi2010]Bounce 弹飞绵羊Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 15763 Solved: 8...
BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊 （动态树LCT）
2002: [Hnoi2010]Bounce 弹飞绵羊Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 2843 Solved: 1519[Submit][Status]Description某天，Lostmonkey发明了一种超级弹力装置，为了在他的...
HDU 5002 Tree（动态树LCT）（2014 ACM/ICPC Asia Regional Anshan Online）
Problem DescriptionYou are given a tree with N nodes which are numbered by integers 1..N. Each node is associated with an integer as the weight.Your t...
动态树LCT(Link-cut-tree)总结+模板题+各种题目
一、理解LCT的工作原理先看一道例题：让你维护一棵给定的树，需要支持下面两种操作：Change x val: 令x点的点权变为valQuery x y: 计算x,y之间的唯一的最短路径的点权的xor和这是一道树剖裸题。我们知道，当题目中出现了维护与树上最短路相关的区间操作时，基本可以确定要用树剖...
hdu 5002 (动态树lct)
TreeTime Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 920 Accepted Submission(s): 388Problem...