「ZJOI2018」 历史
题目链接题目描述有一个一号点为根的有根树 初始时所有点均无颜色。定义对某个点的操作是将这个点到根的所有路径涂上和这个点编号相同的颜色。定义一次这样的操作的收益是这个点到根上的路径与这个点颜色不同的颜色种类个数（未涂过的不算）现在你知道了每个点最多只行了多少次这种操作 让你安排一种操作顺序 使得收益最大。带修改。题解这个题意看起来花里胡哨，我们先考虑如何转化这个题意。每个点到根的路径涂上新颜色...
题目链接题目描述有一个一号点为根的有根树 初始时所有点均无颜色。定义对某个点的操作是将这个点到根的所有路径涂上和这个点编号相同的颜色。定义一次这样的操作的收益是这个点到根上的路径与这个点颜色不同的颜色种类个数（未涂过的不算）现在你知道了每个点最多只行了多少次这种操作 让你安排一种操作顺序 使得收益最大。带修改。题解这个题意看起来花里胡哨，我们先考虑如何转化这个题意。每个点到根的路径涂上新颜色...
题目链接题意一棵有根树 初始时每个点有一个颜色 并且所有点颜色不同 定义路径长度为路径上不同颜色的个数，定义一个点的权值为这个点到根的路径的长度，支持以下操作：将某一个点到根的路径所有的点替换成一种全新的颜色询问某一个点子树权值的平均值题解2操作实际上也就是求和。。我们观察一下1操作一个很自然的想法是修改是把颜色相同的缩起来一块跳。每次执行的操作就是：跳到当前颜色的根->修改->...
众所周知 LCT 可以用来维护动态树的点权信息，但是总有一些题目让你维护动态树上的子树信息或者是链信息，就在这里拿一道经典的题目讲一讲。<h2>「UOJ207」共价大爷游长沙</h2>题目链接题目要求维护动态树和一个路径集合，询问某一条边是否被路径集合中所有的路径经过。首先我们考虑一下树是静态的怎么做：显然我们可以yy出一个随机化算法，我们可以对于每一条路径 $(u,...
<h2>题目描述</h2>题目链接某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$...
题目链接题目简述给定 $N$ 个点 $M$ 条边的无向图，每条边有两个权值 $a$ 与 $b$ 。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。$ n \leq 50000,m \leq 100000$。解题报告乱入：这个题目只需要枚举 a 然后动态加边跑 SPFA 就可以了。 请不要用一个时间复杂度是 $O(nm)$ 的算...