HDU 4010 Query on The Trees (动态树)(Link-Cut-Tree)
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=4010 题意; 先给你一棵树，有 \(4\) 种操作： 1、如果 \(x\) 和 \(y\) 不在同一棵树上则在\(x-y\)连边. 2、如果 \(x\) 和 \(y\) 在同一棵树上并且 \(x!=y...
【BZOJ】洞穴勘测-Link-cut-tree
传送门：BZOJ洞穴勘测 LCT教程：LCT（Link-Cut Tree）详解（蒟蒻自留地） 题意 辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞...
动态树（Link-Cut-Tree）结构与实现简讲
下面分析一下LCT的构建和应用（要用到splay，不会的建议先学splay）： 首先先了解LCT的用处：支持一系列树的操作，如合并，分裂，换根，查询节点数，判断是否在一棵树里，判断深度，甚至还可以当LCA用；下面讲讲做法： 要学LCT首先要清楚几个概念：轻重边，重儿子，辅助树，以及一系列东西，，，我...
LCT模板（link-cut-tree）
#include<stdio.h> #include<algorithm> #define N 200005 using namespace std; //struct stp{int x,y,a,b;}a[N]; //bool cmp(stp a,stp b){r...
浅谈Link-Cut-Tree（[林可砍树]LCT动态树）附例题 Hdu4010
其实一直对LCT很好奇，到底是个什么数据结构可以搞这么多东西，还可以动态地维护，支持加边，合并树，查询等操作，比链剖要强大很多 学过链剖的同学应该可以很快地理解LCT的思路，LCT的实现需要构造辅助树，我们通常选用splay，因为splay方便的序列操作使得LCT的实现显得得心应手，...
Link-Cut-Tree 学习笔记
花了挺长的时间学了LCT，还不是很熟练，还要继续写一些题来熟练。 给初学者的建议： 1、首先先学会链剖和splay，并能掌握它们的原理，熟练写模板。 2、了解LCT和链剖定义的不同，明确Access/Reverse操作各自的作用和原理。 3、在理解操作的原理之后，研究Link/Cut/F...
学习笔记-动态树Link-Cut-Tree
--少年你有梦想吗？--少年你听说过安利吗？ 安利一个集训队讲解：http://wenku.baidu.com/view/75906f160b4e767f5acfcedb 关于动态树问题，有多种方法。。LCT是其中比较常用的方法； LCT这种东西根本没用----by ShallWe----你...
BZOJ 2631 tree 动态树(Link-Cut-Tree)
题目大意：维护一种树形数据结构，支持以下操作： 1.树上两点之间的点权值+k。 2.删除一条边，增加一条边，保证加边之后还是一棵树。 3.树上两点之间点权值*k。 4.询问树上两点时间点的权值和。 思路：利用动态树维护这棵树，lct的裸题。如果不会下传标记的，先去做BZOJ1798，也是这样的标记...
【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊 link-cut-tree
2016-05-30 11:51:59用一个next数组，记录点x的下一个点是哪个查询时，moveroot(n+1),access(x),splay(x) ,输出size[ch[x][0]]即为答案更改时，cut(x,next[x]) link(x,min(x+k,n+1))记得splay旋转后要更...
LOJ #2831. 「JOISC 2018 Day 1」道路建设 线段树+Link-cut-tree
用 LCT 维护颜色相同连通块，然后在线段树上查一下逆序对个数就可以了.code:#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define N 100...
[学习笔记]动态树Link-Cut-Tree
参考&&推荐：LCT总结——概念篇+洛谷P3690[模板]LinkCutTree(动态树)（LCT，Splay）[Link-Cut-Tree]【学习笔记】一、概括一种支持维护树的森林的算法。采用实链剖分，多棵splay维护每个实链，键值就是节点的深度。即，中序遍历就是这个链从上到下的...
BZOJ-3669 魔法森林 Link-Cut-Tree
意识到背模版的重要性了，记住了原理和操作，然后手打模版残了。。颓我时间......3669:[Noi2014]魔法森林TimeLimit:30SecMemoryLimit:512MBSubmit:1598Solved:956[Submit][Status][Discuss]Description为了...