最近几天打算认真复习LCT,毕竟以前只会板子。正好也可以学点新的用法,这里就用来写做题笔记吧。这个分类比较混乱,主要看感觉,不一定对; 维护森林的LCT 就是最普通,最一般那种的LCT啦。这类题目往往...
\(n \times m\)的算法谁都会吧,注意到每次修改影响的仅是一部分的信息,因此可思考优化。 将每个节点对应一个矩阵\(\begin{bmatrix} g[v][0] & g[v][0] \\ g[v][1] & -\infty \end{bmatrix}\) ,从而 \...
题单: https://www.zybuluo.com/xzyxzy/note/1027479 LuoguP3203 [HNOI2010]弹飞绵羊 动态加边,删边 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm&g...
勉强算是结了个大坑吧或者才开始 #include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <cmath> #define R(a,b,c) for(register int a = (...
LCT总结——应用篇(附题单)(LCT) 一般都是维护链的操作。split即可搞定。 进阶操作的话,处理好辅助树和原树的关系即可搞定。 其实,最大的区别就是,splay随便转,辅助树形态变了,但是原树形态不...
题面 题解 先解决第一个子问题吧,它才是难点 Subtask_1 我们可以先用一个简单的树形DP处理出每棵树内部的dis和,记为dp0[i], 然后再用一个换根的树形DP处理出每棵树内点 i 到树内每个点的距离和,记为dp[i],...
早上考试想用\(LCT\)维护联通块\(size\),现在才发现\(LCT\)的\(size\)有虚实之分 \(Link\)与\(Acess\)中虚实变,干他丫的 \(Splay\)中只是相对关系,没有虚实变,因此不搞它 #include <iostream> #includ...
题面 题解 因为每个点都只能向后跳到一个唯一的点,但可能不止一个点能跳到后面的某个相同的点, 所以我们把它抽象成一个森林。(思考:为什么是森林而不是树?) 子节点可以跳到父节点,根节点再跳就跳飞了。 ...