介绍 点分治用于处理 树上的路径问题。 点分治的主要思想是，对于一棵子树，子树内的所有路径只有两种情况： 不经过根节点 经过根节点 对于第一种，我们可以

这篇 blog 记录一个树状数组上二分的小技巧。 介绍 对于树状数组，我们知道它支持 $O(\log n)$ 内进行如下操作： 单点修改 前缀和查询 现在我们希望它用 $O(\log n)$ 支持第三种操

L. Lost Permutation 题意 交互题。 有一个隐藏的 permutation $\pi$，长度为 $n$。 现在只有一种询问： $? ~f_1 ~f_2 … ~f_n$：给定一个 permutation $f$，系统会回答你一个 permutation $g$，

介绍 两个树同构 $\iff$ 有且仅有一种重新编号方式，使得一棵树的节点重新编号后得到另外一棵树。 • 如果是有根树同构，那么还要额外加一个限制条件：树的节点

定义 树的重心是指： 在一棵无权无根树中，对于每一个点 $u$，计算它所有子树中最大的子树的节点数，这个最大值最小的点 $u$ 就是树的重心。 性质 点 $u$ 为重

K. Addition Robot 题意 给定 $n$ 个字母 $s_1, s_2 …, s_n$，每个字母要么为 $A$ 要么为 $B$。 现在有 $Q$ 个询问，每个询问有两种类型： $1 ~ L ~ R$：将 $i \in [L,R]$ 的所有 $A$ 改成 $

CF1666J Job Lookup 题意 给定一个 $n \times n$ 的矩阵 $c_{ij}$。 求一个BST，使得 $\sum\limits_{i,j} c_{ij} \cdot d_{ij}$ 最小。 其中，$d_{ij}$ 代表节点 $i,j$ 在BST中的距离。 输出这个 BST

A. Access Levels 题意 有 $n$ 个程序员，$m$ 个文档。 给定一个 $n \times m$ 的矩阵 $a$，其中 $a_{ij} = 1$ 表示程序员 $i$ 可以访问文档 $j$，否则不行。 现在我们需要选择一个数

介绍 线性规划问题一般表示为如下： 给定 $c_j, a_{ij}, b_i$，求 $x$ 的值使得 $$\max_x \sum_{j=1}^d c_jx_j$$ 其中 $$\sum_{j=1}^d a_{ij} x_j \leq b_i, \forall i = 1…n$$ $$x_j \geq 0, \forall j = 1…d$$ 等价的，可以把上式写作： $$\max_x ~ c \cdot x$$ 其

介绍 KMP算法能在 $O(n)$ 的时间内，求出一个字符串的每个前缀的最长 border 长度。 利用 border 的性质，也可以在 $O(n)$ 的时间内，求出一个字符串 $t$ 在文本串 $s$ 中出现的所有