【BZOJ3669】【NOI2014】魔法森林 LCT
题目描述给你一个\(n\)个点\(m\)条边的图，每条边有两个边权\(a,b\)。请你找出从\(1\)到\(n\)一条路径，使得这条路径上边权\(a\)的最大值\(+\)边权\(b\)的最大值最小。\(n\leq50000,m\leq100000\)题解我们可以考虑求出当边权\(a\leq\)某个数...
与图论的邂逅04：LCT
本着对数据结构这一块东西的一股兴趣，最近在集训的百忙之中抽空出来学LCT，终于学懂了这个高级玩意儿。前置知识：Splay和树链剖分Splay挺复杂的......这里就先不写，不然篇幅太大。树链剖分倒是可以大致地讲一下。树链剖分什么是树链剖分呢？就是把树给解剖成一条条的链子啦~那就先从最常用的重链剖分...
CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表
CF1039ESummerOenotheraExhibitionLG传送门根号分治好题。可以先看我的根号分治总结。题意就是给出长度为\(n\)的区间和\(q\)组询问以及一个\(w\)，每次询问一个\(k\)，问最少把一段给定区间划分几次可以满足每一段划分出的子区间的极差不超过\(w-k\)（以下默...
bzoj 3669: [Noi2014]魔法森林 (LCT）
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3669题面：3669:[Noi2014]魔法森林TimeLimit: 30Sec MemoryLimit: 512MBSubmit: 3928 Solved: 2524[Submit][St...
BZOJ 3669: [Noi2014]魔法森林( LCT )
排序搞掉一维,然后就用LCT维护加边MST.O(NlogN)--------------------------------------------------------------------------------------#include<cstdio>#include<...
动态树LCT
#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>usingnamespacestd;constintmaxn=+,INF=-1u>>;intv[maxn...
洛谷P4338 [ZJOI2018]历史（LCT，树形DP，树链剖分）
洛谷题目传送门ZJOI的考场上最弱外省选手T210分成功滚粗。。。。。。首先要想到30分的结论说实话Day1前几天刚刚刚掉了SDOI2017的树点涂色，考场上也想到了这一点想到了又有什么用？反正想不到最大的贡献是怎么推出来的然后晚上心中怀着九条CNM看完了Solution.pdf貌似对我这个蒟蒻来说...
bzoj 2002 LCT
LCT最基础的题，就用到了一个ACCESS操作首先我们将这个绵羊弹飞的情况看成一颗树，那么假设X点被弹飞到Y点，那么Y为X的父亲节点，弹飞的话父亲节点为n+1（虚设）那么每个询问就是询问X点到根节点n+1的路径长度（节点数）每个修改操作就是将以X为根节点的子树和X的父亲断开，连接到Y上这样简单的维护...
BZOJ5212 ZJOI2018历史（LCT）
首先相当于最大化access的轻重边交换次数。考虑每个点作为战场（而不是每个点所代表的国家与其他国家交战）对答案的贡献，显然每次产生贡献都是该点的子树内（包括自身）此次access的点与上次access的点在该点不同儿子的子树内。假设得到了最后的崛起序列，可以发现相互不包含的子树的贡献是相互独立的，...
Bzoj 1036: [ZJOI2008]树的统计Count 树链剖分,LCT
1036:[ZJOI2008]树的统计CountTimeLimit: 10Sec MemoryLimit: 162MBSubmit: 11102 Solved: 4490[Submit][Status][Discuss]Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个...
[NOI2014]魔法森林 LCT
题面[NOI2014]魔法森林题解一条路径的代价为路径上的\(max(a[i])+max(b[i])\),因为一条边同时有$a[i],b[i]$2种权值，直接处理不好同时兼顾到，所以我们考虑一个暴力的做法。一个暴力的做法：我们枚举\(max(a[i])\),然后强制只能选满足这个限制的边，那么此时\...
洛谷P4219 [BJOI2014]大融合（LCT，Splay）
LCT维护子树信息的思路总结与其它问题详见我的LCT总结思路分析动态连边，LCT题目跑不了了。然而这题又有点奇特的地方。我们分析一下，查询操作就是要让我们求出砍断这条边后，x和y各自子树大小的乘积。掌握了LCT如何维护虚子树信息和后，做法就很清晰了。split(x,y)后，输出x的虚子树和+1与y的...
bzoj 3669: [Noi2014] 魔法森林 LCT版
Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当...
BZOJ 3669 [Noi2014]魔法森林（贪心+LCT）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3669【题目大意】给出一张图，每条边上有两个值ai和bi，现在需要求出一条1到N的路，求使得路上ai的最大值与bi的最大值的和最小。【题解】我们按照ai的权值从小到大排序，依次加边，我们只...
[BZOJ 3669] [Noi2014] 魔法森林 【LCT】
题目链接：BZOJ-3669题目分析如果确定了带x只精灵A，那么我们就是要找一条1到n的路径，满足只经过Ai<=x的边，而且要使经过的边中最大的Bi尽量小。其实就是一个按照Bi建立的MST上1到n的路径。只能使用Ai<=x的边。那么，如果我们从小到大枚举x，这样可以使用的边就不断增加，就...
BZOJ 3669: [Noi2014]魔法森林 [LCT Kruskal | SPFA]
题目描述为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含n个节点m条边的无向图，节点标号为1,2,3,…,n，边标号为1,2,3,…,m。初始时小E同学在1号节点，隐士则住在n号节点。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪...
[Sdoi2017]树点涂色 [lct 线段树]
[Sdoi2017]树点涂色题意：一棵有根树，支持x到根染成新颜色，求x到y颜色数，求x子树里点到根颜色数最大值考场发现这个信息是可减的，但是没想到lct特意设计成lct的形式！如何求颜色数？维护一个点和父亲的颜色是否一样，不一样为1，就是前缀和。考虑相邻的思想和那道“水位线”有点像x到y的答案就是...
BZOJ3091城市旅行——LCT区间信息合并
题目描述输入输出样例输入4513251213244241242343141414样例输出16/36/1提示对于所有数据满足1<=N<=50,0001<=M<=50,0001<=Ai<=10^61<=D<=1001<=U,V<=N前三个操作都...
BZOJ2843 极地旅行社 LCT
欢迎访问~原文出处——博客园-zhouzhendong去博客园看该题解题目传送门-BZOJ2843题意概括有n座岛每座岛上的企鹅数量虽然会有所改变，但是始终在[0,1000]之间。你的程序需要处理以下三种命令：1."bridgeAB"——在A与B之间建立一座大桥（A与B是不同的岛屿）。由于经费限制，...
沉迷Link-Cut tree无法自拔之：[BZOJ2049]洞穴勘探(蒟蒻的LCT板子)
来自蒟蒻\(Hero\_of\_Someone\)的\(LCT\)学习笔记最近学了一波\(LCT\),于是怒刷\(LCT\)合集......$$学的时候借鉴了Clove_unique的博客以及PoPoQQQ的PPT写得很详细,初学者可以去看看...$$先甩一道板子题...$$辣鸡得不能再辣鸡的题.....