Loading...
NOI2021 加油！
<h2>题目描述</h2>题目链接某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$...
点分治是什么： 首先选取一个点将无根树转为有根树，再递归处理每一棵以根节点的儿子为根的子树。 这样得到的分治结构有何用处？ 通俗地讲，对任一个点，树的任一条路径要么经过这个点，要么不经过这个点，在这个点的子树里面。这对于树路径的计数等问题能够更容易的解决。 我们先详细介绍如何点分治，再来继续考虑使用。 考虑到我们每一次选择分治中心的时候，我们希望选出的这个根分出的子树的大小都尽量的小，我们可...
首先什么是启发式算法？启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 最简单的就是并查集的按秩合并，每次把小的合并到大的上面，这样找父亲的复杂度就小了很多。 树上启发式合并（dsu on tree）是一种我也不知道为什么叫做这个名字的奇怪算法。 特点是可以在 $O(nlogn)$ 的时间内完成对无修改的子树的统计。 我们考虑这样一个问题：给树上的每一个节点一个颜色，询问每个节点上的...
题目链接题目描述给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作，要么修改一个点的点权，要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径，路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $.题解问的是所有可能路径上的最小点权的最小值，那我们来考虑一下路径的性质。 首先我们可以发现，如果将这个图分成几个点双联通分量的话，路径一定是经过了从 $s$...
点双连通分量点双连通图：如果一个无向图上没有割点，那么该图为点双连通图。显然有一个性质是同一个点双连通图中任意两点至少存在两条不经过重复点的路径。 点双连通分量：一个无向图的极大点双连通子图 我们可以使用 Tarjan 求解。 大家肯定都会无向图求割点了，我们其实只需要稍微改一下就可以了。 我们可以发现割点是两个点双的分割点，所以我们用栈来保存按照 $dfn$ 排序的目前还能进入新的点双里的...