动态树LCT
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=+,INF=-1u>>...
BZOJ2002[Hnoi2010]弹飞绵羊——LCT
题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵...
洛谷P4338 [ZJOI2018]历史（LCT，树形DP，树链剖分）
洛谷题目传送门ZJOI的考场上最弱外省选手T2 10分成功滚粗。。。。。。首先要想到30分的结论说实话Day1前几天刚刚刚掉了SDOI2017的树点涂色，考场上也想到了这一点想到了又有什么用？反正想不到最大的贡献是怎么推出来的然后晚上心中怀着九条CNM看完了Solution.pdf貌似对我这个蒟蒻来...
bzoj 2002 LCT
LCT最基础的题，就用到了一个ACCESS操作首先我们将这个绵羊弹飞的情况看成一颗树，那么假设X点被弹飞到Y点，那么Y为X的父亲节点，弹飞的话父亲节点为n+1（虚设）那么每个询问就是询问X点到根节点n+1的路径长度（节点数）每个修改操作就是将以X为根节点的子树和X的父亲断开，连接到Y上这样简单的维护...
【BZOJ4817】[Sdoi2017]树点涂色 LCT+线段树
【BZOJ4817】[Sdoi2017]树点涂色DescriptionBob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：1 x:把点x到根节点的路径...
【bzoj4817】树点涂色 LCT+线段树+dfs序
DescriptionBob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：1 x:把点x到根节点的路径上所有的点染上一种没有用过的新颜色。2 x y:...
一堆LCT板子
搞了一上午LCT，真是累死了……以前总觉得LCT高大上不好学不好打，今天打了几遍感觉还可以嘛= =反正现在的水平应付不太难的LCT题也够用了，就这样好了，接下来专心搞网络流。话说以前一直YY不出来LCT怎么维护边权，多谢sxysxy告诉我要添虚点来把边权转化为点权，感激不尽……言归正传。[国家集训队...
【LCT】【QTREE5】Query on a tree V
http://www.spoj.com/problems/QTREE5/en/ 看别人代码理解的LCT。。。 加入set维护虚边 想了好久，终于明白up()函数是什么意思了。。。。 不明白为什么可以没有flip，而且根本不会加flip #include <cstdio>#inclu...
BZOJ3669 膜法森林 - LCT
Solution非常妙的排序啊。。。仔细想想好像确实能够找出最优解QUQ先对第一关键字排序， 在$LCT$ 维护第二关键字的最大值 所在的边。添边时如果$u, v$ 不连通 就直接加边。 如果连通 并且路径上的最大值 大于 当前边 的 第二关键字， 那么可以换掉。如果 $1$ 和 $N$ 连通 就...
【BZOJ3091】城市旅行 LCT
【BZOJ3091】城市旅行DescriptionInputOutputSample Input4 51 3 2 51 21 32 44 2 41 2 42 3 43 1 4 14 1 4Sample Output16/36/1HINT对于所有数据满足 1<=N<=50,000 1<...
BZOJ5212 ZJOI2018历史（LCT）
首先相当于最大化access的轻重边交换次数。考虑每个点作为战场（而不是每个点所代表的国家与其他国家交战）对答案的贡献，显然每次产生贡献都是该点的子树内（包括自身）此次access的点与上次access的点在该点不同儿子的子树内。假设得到了最后的崛起序列，可以发现相互不包含的子树的贡献是相互独立的，...
BZOJ_2594_[Wc2006]水管局长数据加强版_LCT
BZOJ_2594_[Wc2006]水管局长数据加强版_LCTDescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的...
Bzoj 1036: [ZJOI2008]树的统计Count 树链剖分,LCT
1036: [ZJOI2008]树的统计CountTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 11102 Solved: 4490[Submit][Status][Discuss]Description一棵树上有n个节点，编号分别为1到n，每个节...
bzoj 3669: [Noi2014]魔法森林 (LCT）
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3669题面：3669: [Noi2014]魔法森林Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 3928 Solved: 2524[Submi...
UOJ#374. 【ZJOI2018】历史 贪心,LCT
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ374.html题解想出正解有点小激动。不过因为傻逼错误调到自闭。不如贺题首先我们考虑如何 $O(n)$ 求一个答案。首先，计算两条路径的贡献时，由于两国连续交战数次只算一次，所以我们可以只看这两条路径的交的...
「ZJOI2018」历史（LCT）
「ZJOI2018」历史（LCT）\(ZJOI\) 也就数据结构可做了……题意：给定每个点 \(access\) 次数，使轻重链切换次数最大，带修改。\(30pts:\)挺好想的。发现切换次数只跟子树中所有结点的 \(access\) 次数，可以树形 \(dp\)。假设 \(x\) 有 \(m\) ...
【loj6038】「雅礼集训 2017 Day5」远行 树的直径+并查集+LCT
题目描述给你 $n$ 个点，支持 $m$ 次操作，每次为以下两种：连一条边，保证连完后是一棵树/森林；询问一个点能到达的最远的点与该点的距离。强制在线。$n\le 3\times 10^5$ ，$m\le 5\times 10^5$ 。题解树的直径+并查集+LCT与直径相关的结论1：与一个点距离最大...
【lct】bzoj2049 [Sdoi2008]Cave 洞穴勘测
题意：维护一个动态并查集，支持加边，删边，维护两点连通性。 主要用到了 lct 的 Access FindRoot ChangeRoot link cut 操作。 #include<cstdio>#include<iostream>#include<stack>...
LuoguP4234_最小差值生成树_LCT
LuoguP4234_最小差值生成树_LCT题意：给出一个无向图，求最大的边权减最小的边权最小的一棵生成树。分析：可以把边权从大到小排序，然后类似魔法森林那样插入。如果两点不连通，直接连上，否则找到两点间最大的边权替换。如果生成一棵树了就更新答案。LCT维护边权的最大值即可。代码：// luogu-...
Cogs 1688. [ZJOI2008]树的统计Count(树链剖分+线段树||LCT)
[ZJOI2008]树的统计Count ★★★ 输入文件：bzoj_1036.in 输出文件：bzoj_1036.out 简单对比 时间限制：5 s 内存限制：162 MB 【题目描述】 一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式...