石子移动
考虑将操作过程倒过来，最后值域在 $[l, r]$ 内的在上一步应该也是一个区间，便可得出最初的区间限制。
时间复杂度 $\Theta(n + q)$。
分数排序
$n$ 阶 Farey 数列可以直接在 stern-brocot 树上遍历：初始设置 $\frac ab = \frac 01, \frac xy = \frac 11$。那么 $(\frac ab, \frac xy)$ 这一节点的左子和右子分别为 $(\frac ab, \frac {a+x}{b+y}), (\frac{a+x}{b+y}, \frac xy)$。不难证明任何出现的一个分数的分子分母都是互质的，且这样可以遍历所有分数。
考虑如何在这个树上找到一个分数，虽然一个节点到根的距离可以是 $\Theta(n)$ 的（例如 $\frac 1n$），但是假设我们走到 $(\frac ab, \frac{a+x}{b+y})$ 叫做 $L$ 操作，否则叫做 $R$ 操作，那么一个节点对应找到它的操作序列的连续段数应该是 $\mathcal O(\log n)$ 的，因为一次 $LR$ 会使得分母倍增。我们可以倍增看操作序列一共下一组 $L$ 或者 $R$ 有多长，因此我们会进行 $\mathcal O(\log^2 n)$ 次 check 操作。
考虑如何计算一次 check： $$ \begin{eqnarray} & &\sum_{x\le n} \sum_{y\le n} \left[\frac xy \le \frac ab\right] [\gcd(x, y) = 1]\\ &= & \sum_{x\le n} \sum_{y\le n} \left[\frac xy \le \frac ab\right] \sum_{d | (x, y)} \mu(d)\\ &= & \sum_d \mu(d) \sum_{y\le \frac nd} \sum_{x\le \frac nd} \left[x \le \frac {ay}b\right] \\ &= & \sum_d \mu(d) \sum_{y = 1}^{\left\lfloor\frac nd\right\rfloor} \min\left( \left\lfloor \frac nd \right\rfloor, \left\lfloor \frac{ay}b \right\rfloor \right) \end{eqnarray} $$ 对 $\left\lfloor\frac nd\right\rfloor$ 除法分块，我们需要 $\mu(d)$ 在这些位置的前缀和，而 $\sum_{y = 1}^{\left\lfloor\frac nd\right\rfloor} \min\left( \left\lfloor \frac nd \right\rfloor, \left\lfloor \frac{ay}b \right\rfloor \right)$，这个式子在一个前缀中取得右边是较小值，这部分我们可以通过类欧几里得算法在 $\Theta(\log b)$ 时间内计算。因此我们一次 check 的时间消耗为 $\Theta(\sqrt n \log n)$。注意前缀和的处理可以使用 $\Theta(n^{\frac 23})$，但是在本题限制下 $\Theta(n)$ 也是 ok 的。
综上所述，时间复杂度为 $\Theta(n^{\frac 23}) + \Theta(\sqrt n \log^3 n)$。
彼岸蔷薇
newbiedmy 这家伙会乱搞，很有毒！
关于背景
那段歌词摘自遗忘山丘。
算法一
考虑枚举所有路径，对于每个情况按照定义求出最大路径数。
显然最大路径数可以通过树形 dp 进行计算。$f(u)$ 表示考虑所有两端点均在 $u$ 的子树的路径，此时的最大答案。此时分成两类转移情况讨论，要么选择的路径均不经过 $u$，那么这一情况的最优解即 $u$ 的所有直系孩子的 $f$ 之和。否则枚举选取哪个路径，这一情况的贡献是 $1$ 加上与这条路径相邻的所有节点的 $f$ 之和。
时间复杂度 $\Theta(mn^3)$，预计得分 $32\%$。
算法二
考虑优化 dp 的效率，我们记 $g(u)$ 为 $f(u)$ 减去其所有直系孩子的 $f$，则不难发现 $g(u)$ 对于路径情况的转移就是所选路径上 $g$ 的和再加 $1$。通过一个树状数组即可维护。
时间复杂度 $\Theta((n + m\log n)n^2)$，预计得分 $40\% \sim 44\%$。
算法三
我们对于计算最大路径数有两种不同角度的观察：
- 显然 $g$ 的值要么为 $0$ 要么为 $1$，这表示事实上 $g$ 就是代表达到子树中最优解是否必须有一条路径穿过 $u$，这当且仅当存在一条路径经过的 $g$ 均为 $0$。
- 这也可以看成一个贪心，我们仅仅是按照路径的 lca 自底向上贪心，能放就放。
考虑通过这种贪心思路来计算解，我们只需在 dfs 的过程中额外维护一个 vis 数组，表示“这个节点是否上面有一个父亲已经作为某条被选择路径的 lca”。未被染色的节点显然时刻都是与根节点相连的一个连通块。我们每次选择一条路径，只需把该节点子树中与之相邻的未被染色的节点染色。检查一条路径的时候，只需检查两端点是否均未被染色。这样就可以做到线性。
时间复杂度 $\Theta((n + m)n^2)$，预计得分 $44\%$。
算法四
我们提出如下观察：假设一个节点 $u$ 满足加入路径 $(u,u)$ 能够使得最大路径数增加，则称节点 $u$ 是 ok 的。那么一条路径加入后能使最大路径数增加，当且仅当路径上的节点都是 ok 的。
之前的过程中我们对于根的选择是任意性的，接下来我们考虑以一个节点为根的时候，穿过它的路径如果能够增大最大路径数，此时显然等价于路径上的节点均未被选中，也就是在贪心过程中这条路径就可以被选。
我们考虑染色之后与根节点联通的未被染色的连通块，这应当与与 $u$ 相邻的 ok 的节点所构成的的连通块是一致的。因为我们考虑在未被染色的这个连通块内进行换根，其他子树必然没有发生结构变化所以染色情况不变，因此穿过这个连通块的所有路径均不能选，在这个情况下染色数组完全没有变化，因此这个连通块的任何一个节点都是 ok 的。
我们只需以每个点为根进行一次算法三的操作，然后对于每个连通块，对答案的贡献就是连通块大小的平方。
时间复杂度 $\Theta((n+m)n)$，预计得分 $60\%$。
算法五
我们如何快速计算一个节点是否 ok。注意到贪心选择出的每条路径的 LCA，在任何一组最大路径集合中，这些节点都必然各自被一条路径覆盖。因此我们考虑将贪心选择出的每个路径及其 LCA 作为基础，发现在 LCA 的子树中的，不经过其他 LCA 的这一连通块内部，不 ok 的节点显然是该 LCA 对应的路径的一个子段。为了注意到为了让一颗子树里的节点不被覆盖，我们可以通过更换路径使得新的不与其他路径冲突的路径，用于更新原本路径 ok 的部分。注意在此时可以牺牲上方的空间，因此这个思路必须是自顶向下更新的。
因此两类路径可以用于更换被选路径：
- 该路径的 LCA 是 ok 的，此时显然这一路径已经与某条路径相交，如果只与一条路径相交，则可以更新该路径。
- 该路径的 LCA 和某个 LCA 重合，且不与其它路径相交，此时可以更新该路径。
对于如何快速判断一条路径是否只与一条路径相交，与哪条路径相交，我们可以打一个标记分为 $0, v, -1$，表示这一节点向上被选择的 LCA 有 $0$ 个，有 $1$ 个并标记其编号，或者有 $\ge 2$ 个。这样只需通过 DFS 即可更新标记，且一个节点只会被更新 $2$ 次。
通过离线处理，我们可以做到时间复杂度 $\Theta(n + m\alpha(m,n))$，如果使用 $\Theta(n)-\Theta(1)$ LCA 技术也可以做到 $\Theta(n+m)$，预计得分 $100\%$。
