BZOJ 3669 [Noi2014]魔法森林（贪心+LCT）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3669【题目大意】给出一张图，每条边上有两个值ai和bi，现在需要求出一条1到N的路， 求使得路上ai的最大值与bi的最大值的和最小。【题解】我们按照ai的权值从小到大排序，依次加边...
BZOJ 3669: [Noi2014]魔法森林 [LCT Kruskal | SPFA]
题目描述为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜...
【BZOJ3669】【NOI2014】魔法森林 LCT
题目描述给你一个\(n\)个点\(m\)条边的图，每条边有两个边权\(a,b\)。请你找出从\(1\)到\(n\)一条路径，使得这条路径上边权\(a\)的最大值\(+\)边权\(b\)的最大值最小。\(n\leq 50000,m\leq 100000\)题解我们可以考虑求出当边权\(a\leq\)某...
洛谷P4219 [BJOI2014]大融合（LCT，Splay）
LCT维护子树信息的思路总结与其它问题详见我的LCT总结思路分析动态连边，LCT题目跑不了了。然而这题又有点奇特的地方。我们分析一下，查询操作就是要让我们求出砍断这条边后，x和y各自子树大小的乘积。掌握了LCT如何维护虚子树信息和后，做法就很清晰了。split(x,y)后，输出x的虚子树和+1与y的...
[BZOJ 3669] [Noi2014] 魔法森林 【LCT】
题目链接：BZOJ - 3669题目分析如果确定了带 x 只精灵A，那么我们就是要找一条 1 到 n 的路径，满足只经过 Ai <= x 的边，而且要使经过的边中最大的 Bi 尽量小。其实就是一个按照 Bi 建立的 MST 上 1 到 n 的路径。只能使用 Ai <= x 的边。那么，如...
[转]LCT讲解
LCT（1）维护一个序列，支持下列操作：区间求和 区间求最值 区间修改 求连续子段和 这个线段树就可以解决 具体做法不加累述了 （2）维护一个序列，支持下列操作： 区间求和 区间求最值 区间修改 求连续子段和 添加一段区间 删除一段区间 翻转一段区间 Splay的基本操作 （3）维护一棵树，支持下列...
BZOJ3091 城市旅行 LCT
欢迎访问~原文出处——博客园-zhouzhendong去博客园看该题解题目传送门 - BZOJ3091题意概括鉴于本人语文不好，此题的描述原题很清晰，废话不多，请看原题。可怕，原题是图片，不可以复制题目+删掉废话了……题解http://blog.csdn.net/popoqqq/article/de...
【LCT】BZOJ3091 城市旅行
3091: 城市旅行Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1927 Solved: 631[Submit][Status][Discuss]DescriptionInputOutputSample Input4 51 3 2 51 21 3...
【Luogu】P4172水管局长（LCT）
题目链接有个结论是x到y的路径上最长边权值等于最小生成树上最长边权值，于是问题转化为最小生成树。再考虑把问题反过来，删边变成加边。于是变成动态维护最小生成树，LCT可以做到。#include<cstdio>#include<cstdlib>#include<algori...
浅谈Link-Cut-Tree（[林可砍树]LCT动态树）附例题 Hdu4010
其实一直对LCT很好奇，到底是个什么数据结构可以搞这么多东西，还可以动态地维护，支持加边，合并树，查询等操作，比链剖要强大很多 学过链剖的同学应该可以很快地理解LCT的思路，LCT的实现需要构造辅助树，我们通常选用splay，因为splay方便的序列操作使得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...
hdu 5398 动态树LCT
GCD TreeTime Limit: 5000/2500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 415 Accepted Submission(s): 172Prob...
Fzu Problem 2082 过路费 LCT,动态树
题目：http://acm.fzu.edu.cn/problem.php?pid=2082Problem 2082 过路费 Accept: 528 Submit: 1654Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Desc...
SB40100LCT-ASEMI大功率肖特基二极管SB40100LCT
编辑-ZSB40100LCT在TO-220AB封装里采用的2个芯片，其尺寸都是120MIL，是一款大功率肖特基二极管。SB40100LCT的浪涌电流Ifsm为200A，漏电流(Ir)为40uA，其工作时耐温度范围为-40~150摄氏度。SB40100LCT采用金属硅芯片材质，里面有2颗芯片组成。SB...
[ZJOI2016]大森林(LCT)
题目描述小Y家里有一个大森林，里面有n棵树，编号从1到n。一开始这些树都只是树苗，只有一个节点，标号为1。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。小Y掌握了一种魔法，能让第l棵树到第r棵树的生长节点长出一个子节点。同时她还能修改第l棵树到第r棵树的生长节点。她告诉...
【LCT】一步步地解释Link-cut Tree
简介Link-cut Tree，简称LCT。干什么的？它是树链剖分的升级版，可以看做是动态的树剖。树剖专攻静态树问题；LCT专攻动态树问题，因为此时的树剖面对动态树问题已经无能为力了（动态树问题通常夹杂着树的操作，如删边与连边。这是线段树无法应对的）。LCT难写吗？不难写啊...预备知识：Splay...
ASEMI肖特基二极管SB40100LCT参数，SB40100LCT规格书
编辑-ZASEMI肖特基二极管SB40100LCT参数：型号：SB40100LCT最大重复峰值反向电压（VRRM）：100V最大平均正向整流输出电流（IF）：40A峰值正向浪涌电流（IFSM）：200A每个元件的典型热阻（ReJA）：2℃/W工作结和储存温度范围（TJ, TSTG）：-40to +1...
[ZJOI2018]历史（LCT）
这篇还发了洛谷题解[Luogu4338] [BZOJ5212]题解题意给出一棵树,给定每一个点的 \(access\) 次数,计算轻重链切换次数的最大值,带修改.先考虑不带修改怎么做假设 \(u\) 的子树发生了两次 \(access\) , 那么当且仅当这两次 \(access\) 的点来自 \...
P4338 [ZJOI2018]历史 LCT+树形DP
\(\color{#0066ff}{ 题目描述 }\)这个世界有 n 个城市，这 n 个城市被恰好 \(n-1\) 条双向道路联通，即任意两个城市都可以 互相到达。同时城市 1 坐落在世界的中心，占领了这个城市就称霸了这个世界。在最开始，这 n 个城市都不在任何国家的控制之下，但是随着社会的发展，一...
【BZOJ5212】[ZJOI2018] 历史（LCT大黑题）
点此看题面大致题意： 给定一棵树每个节点\(Access\)的次数，求最大虚实链切换次数，带修改。什么是\(Access\)？推荐你先去学一学\(LCT\)吧。初始化（不带修改的做法）首先考虑初始化，即不带修改的做法，貌似这样就有30分了。先要注意到一点：我们可以发现，对于每一个节点，它的答案是独立...