BZOJ3669: [Noi2014]魔法森林(瓶颈生成树 LCT)
Description 为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。 魔法森林中居住了一些妖怪。 ...
程序员文章站2022-12-24（持续更新）LCT(Link-cut-tree) 总结+模板题+各种题目
准备知识：树剖&Splay 一、理解LCT的工作原理 先看一道例题： 让你维护一棵给定的树，需要支持下面两种操作： Change x val: 令x点的点权变为val Query x y: 计算x,y之间的唯一的最短路径的点权的xor和 这是一道树剖裸题。我们知道，当题目中出现了维护与树上最短路相关 ...
程序员文章站2022-12-05洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)
题目描述 小L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做“LCT” 的挑战，它的规则是这样子的：现在有一个N 个点的 树（Tree），每条边有一个整数边权vi ，若vi > ...
程序员文章站2022-12-05洛谷P4719 【模板】动态dp(ddp LCT)
题意 "题目链接" Sol 动态dp板子题。有些细节还没搞懂，待我研究明白后再补题解。。。 cpp include define LL long long using namespace std; const int MAXN = 1e5 + 10, INF = INT_MAX; template ...
程序员文章站2022-11-12浅谈Link-Cut Tree(LCT)
0XFF 前言&概念 Link Cut Tree 是一种用来维护动态森林连通性的数据结构，适用于动态树问题。它采用类似树链剖分的轻重边路径剖分，把树边分为实边和虚边，并用 Splay 来维护每一条实路径。 Link Cut Tree 的基本操作复杂度为均摊O(logn），但常数因子较大，一般效率会低 ...
程序员文章站2022-10-18IT编程Link-Cut-Tree(LCT)详解
前置知识 必须要理解 "splay" 最好学过 "树链剖分" 基础定义 LCT是一种解决动态树问题的方法，由tarjan~~(为什么又是他)~~在1982年提出，最原始的论文在 "这里" ,在论文中，tarjan除了介绍了均摊复杂度为$O(log^2n)$的LCT之外，还介绍了一种严格$O(log^ ...
程序员文章站2022-09-30IT编程BZOJ1969: [Ahoi2005]LANE 航线规划(LCT)
Description 对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。 星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编 ...
程序员文章站2022-07-10IT编程LCT经验总结
~~妈妈，我终于会写LCT了！~~ LCT太神奇了，它和Splay能完美结合。在$O(nlogn)$的时间内解决动态树问题。 BZOJ2049 [Sdoi2008]Cave 洞穴勘测 丢板子，懒得解释。用维护一下联通块就行了，因为数据水，并查集也可以水过。 AC代码： c++ include inc ...
程序员文章站2022-07-02洛谷P3690 【模板】Link Cut Tree （LCT）
题目背景 动态树 题目描述 给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。 0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。 1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。 ...
程序员文章站2022-07-02BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊(LCT)
Description 某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ ...
程序员文章站2022-06-18洛谷P1501 [国家集训队]Tree II(LCT)
题目描述 一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一： + u v c：将u到v的路径上的点的权值都加上自然数c； - u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树； \* u v c：将 ...
程序员文章站2022-06-18（持续更新）LCT(Link-cut-tree) 总结+模板题+各种题目
准备知识：树剖&Splay 一、理解LCT的工作原理 先看一道例题： 让你维护一棵给定的树，需要支持下面两种操作： Change x val: 令x点的点权变为val Query x y: 计算x,y之间的唯一的最短路径的点权的xor和 这是一道树剖裸题。我们知道，当题目中出现了维护与树上最短路相关 ...
程序员文章站2022-05-10IT编程洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)
题目描述 小L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做“LCT” 的挑战，它的规则是这样子的：现在有一个N 个点的 树（Tree），每条边有一个整数边权vi ，若vi > ...
程序员文章站2022-05-10IT编程BZOJ3669: [Noi2014]魔法森林(瓶颈生成树 LCT)
Description 为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。 魔法森林中居住了一些妖怪。 ...
程序员文章站2022-05-08IT编程洛谷P4719 【模板】动态dp(ddp LCT)
题意 "题目链接" Sol 动态dp板子题。有些细节还没搞懂，待我研究明白后再补题解。。。 cpp include define LL long long using namespace std; const int MAXN = 1e5 + 10, INF = INT_MAX; template ...
程序员文章站2022-05-08IT编程友好国度 - 数论 - 容斥 - 并查集/LCT
题目大意：给你一颗树，点有点权，问有多少路径，路径上点权的gcd是1。1e5题解：考虑容斥，转为计数是g的倍数的路径。把所有g的倍数的边（边权是两端点权的gcd）拿出来，每次合并两个集合前用两个集合的大小的乘积对ans[g]有贡献。然后并查集即可啥你问我为啥代码看起来像是个LCT？#include&...
程序员文章站2022-05-08Link-Cut-Tree(LCT)详解
前置知识 必须要理解 "splay" 最好学过 "树链剖分" 基础定义 LCT是一种解决动态树问题的方法，由tarjan~~(为什么又是他)~~在1982年提出，最原始的论文在 "这里" ,在论文中，tarjan除了介绍了均摊复杂度为$O(log^2n)$的LCT之外，还介绍了一种严格$O(log^ ...
程序员文章站2022-04-15IT编程BZOJ1969: [Ahoi2005]LANE 航线规划(LCT)
Description 对Samuel星球的探险已经取得了非常巨大的成就，于是科学家们将目光投向了Samuel星球所在的星系——一个巨大的由千百万星球构成的Samuel星系。 星际空间站的Samuel II巨型计算机经过长期探测，已经锁定了Samuel星系中许多星球的空间坐标，并对这些星球从1开始编 ...
程序员文章站2022-04-15IT编程P1501 [国家集训队]Tree II（LCT 下推标记，LCT 维护树上信息）
用 LCT 维护整棵树，splay 中要维护每个点的权值，子树节点个数以及子树和，为了优化复杂度还要维护下推标记。这题有三种标记：翻转，加法，乘法翻转标记的下推顺序不影响维护值，加法和乘法优先维护乘法下推标记，将乘法下推时要将子节点的子树和，节点权值，加法下推标记和乘法下推标记全部乘上乘法标记加法下...
程序员文章站2022-04-06浅谈Link-Cut Tree(LCT)
0XFF 前言&概念 Link Cut Tree 是一种用来维护动态森林连通性的数据结构，适用于动态树问题。它采用类似树链剖分的轻重边路径剖分，把树边分为实边和虚边，并用 Splay 来维护每一条实路径。 Link Cut Tree 的基本操作复杂度为均摊O(logn），但常数因子较大，一般效率会低 ...
程序员文章站2022-04-05IT编程