我们有这样一个问题：修改点权，询问链上的点权和。这明显是个树链剖分模版。
但如果还有这些操作呢：断开一条边，连上一条边，保证一直是森林。这就是动态树的一种问题。
而 LCT 就是解决这些问题的优秀数据结构。

自来水厂到你家的水管网是一个复杂的有向图，每一节水管都有一个最大承载流量。
水厂不放水，你家就断水了。但是就算水厂拼命的往管网里面注水，你家收到的水流量也有上限（毕竟每根水管承载量有限）。
你想知道你最多能够拿到多少水，这就是一种最大流问题。

luogu 阅读链接。 题目链接。 题目的边用的是倍数关系（偏序）。 当 x→y,y→zx \rarr y, y \rarr zx→y,y→z，就必然有 x→zx \rarr zx→z。 为了避免这种情况，意味着每个点要么只有因数，要么只有倍数。 我们将每个点拆成两个点，x0x_0x0​ 表示图中 xxx 只能保留其的因数，x1x_1x1​ 表示其倍数。 再用一条边 (x,y)(x, y)(...

替罪羊树是一个优雅的暴力，以均摊 O(log(n)) 的时间复杂度和简单的代码闻名。

treap = tree + heap，就比 BST 多了几行代码。

平衡思路超简单，最早发明的自平衡二叉树，也是查询速度最快的平衡树，

luogu 阅读链接。 定义 BST（二叉搜索树）是一种树形结构，有如下性质。 空树是二叉搜索树。 若左子树非空，那么左子树上所有点的权值均小于其根节点的值。 若左子树非空，那么其右子树上所有点的权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 操作 BST 的单次操作最坏为 O(n)O(n)O(n)，nnn 表示 BST 内的节点数，即树的形态是一条链。 节点定义 ...

前言 本文的线性基指异或线性基。 由于作者太菜了本文的语言不会特别规范。 简介 线性基简称基，它是一个数的集合，并且每个序列都拥有至少一个线性基。 线性基有三个性质： 线性基中的几个数异或后不能得到 000。 线性基中的数在异或后能得到原序列中的所有数。 线性基在保证前两个性质时，会使得基内的个数最少。 基本操作 我们用数组 ppp 表示 {ai−1}\{a_{i - 1}\}{a...

luogu 阅读链接。 前言 麻将模拟器 调了一早上结果发现 DP 中的 jjj 写成 iii 了。 题目中的和牌距离基本和向听数差不多。 文中的面子指刻子和顺子的统称。 基础操作 定义 #define endl '\n' #define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a+...

luogu 阅读链接。 灭鼠行动。 前言 其实有很多地方出题人没讲清楚，所以只保证代码可以通过本题数据。 细节 神秘射线是停止一切生理活动（包括成长），会暂停，但不会打断繁殖。 繁殖后要动一下（包括旋转），才能继续繁殖。 顺序：武器 -> 繁殖 -> 移动。 注意老鼠刚出生时的年龄。 注意时间单位和时刻的区别。 繁殖是某点恰好有两只异性老鼠。 岔路的拐弯与当前这只老鼠面对岔...