这实际上是一个 Tarjan 求割点的裸题。 具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后 …
lp4430 猴子打架/Prufer 序列
额…看起来是一道找规律题,实际上还是挺有门道的。 题目的题意就是,求 n 个点的点、边均有标号的生 …
lp4577 FJOI2018 领导集团问题
我们尝试类比序列上的情况来看这一题。 对于序列上的情况,我们维护一个集合 ,其中 表示,长度为 的 …
CF1009F Dominant Indices
首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。 它本质上就是一种优化的暴力:对 …
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp4768 NOI2018 归程
克鲁斯卡尔重构树模板题。 我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点; …
lp3302 SDOI2013 森林
我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出 …
lp2515 HAOI2010 软件安装
简单的tarjan缩点+树形背包DP。 考虑N<=100,M<=500,只需要设f[i][j]表示 …
lp3233 HNOI2014 世界树
让我们来分析这道题。 我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优 …
lp2146 NOI2015 软件包管理器
简化题意: 存在一棵树,其上所有点的初始值为0。 存在两种操作,分别是,将一个点的所有父亲节点改为1,或者将一 …
lp2486 SDOI2011 染色
考虑这一题在链上的情况。 显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。 …
lp5290 十二省联考2019 春节十二响
首先我们考虑一种n^2logn的做法:将所有的子程序根据内存消耗来排序,然后每一次选中内存消耗最大且尚未被选中 …
lp2590 ZJOI2008 树的统计
树剖套线段树裸题。
lp3950 部落冲突
LCT裸题。
lp4582 FJOI2014 树的重心
两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发 …
lp4332 SHOI2014 三叉神经树
我们知道,每一个\(x_{i}\)各不相同。这启发我们,这一题的点将形成一棵树的结构。 仔细观察题目描述,我们 …
lp1501 国家集训队 Tree II
如果没有操作2,就是树链剖分套线段树的裸题了。 但是操作2让这题变得麻烦了很多。 考虑LCT。我们知道LCT维 …
lp3203 HNOI2010 弹飞绵羊
依照题意,我们发现,题目求的就是指定点到根的路径长度。 于是,我们对于每一个修改弹力的操作,都可以转化为断边和 …
lp2147 SDOI2008 洞穴勘测
维护链接和断开,LCT裸题,(看起来)也可以用按秩合并优化并查集。
lp3690 【模板】Link Cut Tree (动态树)
树链剖分有多种方法。例如以重量为关键字的重链剖分,以长度为关键字的长链剖分。 而LCT(Link-Cut-Tr …