RainAir
My OI Blog
RainAir

LCT
文章归档

LCT 维护子树信息

众所周知 LCT 可以用来维护动态树的点权信息,但是总有一些题目让你维护动态树上的子树信息或者是链信息,就在这里拿一道经典的题目讲一讲。 「UOJ207」共价大爷游长沙 题目链接 题目要求维护动态树和一个路径集合,询问某一条边是否被路径集合中所有的路径经过。 首…

   476   2019-01-30   476 去吊打作者

「BZOJ2002」「HNOI2010」弹飞绵羊

题目描述 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$,当绵羊达到第 $i$ 个装置时,它会往后弹 $k_i$ …

   522   2019-01-29   522 去吊打作者

「BZOJ 3669」「NOI2014」魔法森林

题目链接 题目简述 给定 $N$ 个点 $M$ 条边的无向图,每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。 $ n \leq 50000,m \leq 100000$。 解题报告 乱入:这个题目只需要枚举 a 然后动…

   528   2019-01-06   528 去吊打作者

Link-Cut-Tree 学习笔记

定义 链剖分 首先我们知道,OI 中能见到的有重链剖分,实链剖分和长链剖分。 重链剖分已经在之前的树链剖分中熟练运用过了,长链剖分不常考,所以这次我们先来看一看实链剖分。 实链剖分:将某一个儿子的连边划分为实边,而连向其他子树的边划分为虚边。 我们发现边…

   454   2019-01-06   454 去吊打作者
标签
近期评论