LCT的进阶应用

关于LCT的进阶应用 不光是写算法思路,因为已经有很多人写过了,更重要的是代码写法中的细节,不然LCT各种奇怪应用的细节够你一题调一个小时 本篇文章将助你考试一遍过样例! 当然,还有一些基础应用比如维护路径信息或者维护联通性,但是代码都相对比较模板,所以也没什么好写 一. LCT维护边双连通分量有些题目中会动态加边并有形如“x到y之间有多少必经边” “某个边双内有多少点”的询问,这时候需要用...

长跑[BZOJ2959]

题目描述某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。为了让同学们更好地监督自己,学校推行了刷卡机制。学校中有$n$个地点,用$1$到$n$的整数表示,每个地点设有若干个刷卡机。有以下三类事件: 修建了一条连接A地点和B地点的跑道。 A点的刷卡机台数变...

我们的CPU遭到攻击[LOJ558]

题目描述给你一个有$n$个点的森林,点有黑白两种颜色,初始时所有点都是白色,森林的每条边有边权,初始时这个森林有$m$条边。 对这个森林进行$k$次操作,操作有三种: L u v w:添加一条连接$u$和$v$,长度为$w$的边。 C u v:删除连接$u$和$v$的边(保证存在)。 F u:反转点$u$的颜色(黑变白,白变黑)。 Q u:询问所有与$u$相连的黑点到$u$的距离之和。...

历史[ZJOI2018]

题目描述&输入/输出格式[ZJOI2018]历史 题解首先,没有修改时的答案可以使用树形DP解决 上图中,红色数字表示$a_x$,蓝色数字表示$x$子树的点权和$sum_x$ 观察点$2$,显然只有$2,5,6$”崛起”时才有可能在$2$发动战争 显然,当操作顺序形如$5,2,5,6$时,会在$2$进行三次战争,为最大值。 再来看点$1$,其实我们可以把$2,5,6$三个点看作一个点...

树点涂色[SDOI2017]

【题目描述】 Bob 有一棵$n$个点的有根树,其中$1$号点是根节点。Bob 在每个点上涂了颜色,并且每个点上的颜色不同。 定义一条路径的权值是:这条路径上的点(包括起点和终点)共有多少种不同的颜色。 Bob可能会进行这几种操作: 1 x 表示把点$x$到根节点的路径上所有的点染上一种没有用过的新颜色。 2 x y 求$x$到$y$的路径的权值。 3 x 在以$x$为根的子树中选择一个点...

魔法森林[NOI2014]

【题目描述】 题目描述又臭又长 简单来说 有一个有$n$个点,$m$条边的无向图,每条边有两个权值$a,b$,从点$u$走到任意一个点$v$的代价是途经的边中最大的$a$加上最大的$b$ 求从点$1$到点$n$的最小代价 【输入格式】 rt,给你一张图 【输出格式】 输出最小代价。如果无法到达,输出-1。 题解如果边权只有一个,那么显然就是建出最小生成树 但是这里有两个 我们可以先以$a$为...