题目非私密模拟，可以公开博客。

Problem 1

取 $G$ 的任一 DFS 树 $T$，考虑一条边 $(u,v) \in E$ 且 $d_u > d_v$，由于 DFS 树中没有横叉边，因此 $u \in \mathrm{subtree}(v)$，考虑删去 $u,v$ 后整棵树会分成以下几个部分：

• $v$ 到根以及上面挂着的部分，记作 $H$。
• $u$ 到 $v$ 路径及上面挂着的部分，记作 $M$。
• $u$ 的所有子树，记作 $L_i$。

问题等价于判断这些部分有没有全部被连在一起。

首先，判断 $H$ 和 $M$ 有没有被连起来是简单的：预处理 $u$ 到其 $2^k$ 次祖先的这一段以及上面挂着的东西中，不算 $u$，连出去的边最高能到哪里。如果这个深度突破了 $v$，那么 $H$ 和 $M$ 就连起来了。

然后考虑 $H$ 和 $L_i$ 的连接。这个也是简单的：DFS 的时候预处理出每个子树里面，连上去最高到哪里，如果突破了 $v$ 就说明连起来了。因此，我们可以把所有边按照 $u$ 分类，然后按照 $v$ 从深到浅的顺序考虑，那么每个 $L_i$ 就会逐渐地和 $H$ 连起来，扫描线即可。

最后就是 $M$ 和 $L_i$。既然我们之前已经按照 $v$ 从深到浅考虑了，所以只要求出 $v$ 深度的临界点即可。这个可以通过将所有 $u$ 按照从浅到深的顺序考虑，然后用一个线段树来查询每个子树往上，最深连到了哪里。

注意几个特殊情况：$H = \varnothing$（$v$ 是根），$M = \varnothing$（$v$ 是 $u$ 的父亲）和都是空的。前面两个都可以直接处理；都是空的的情况分类讨论一下就好了，因为这个时候可能会有不在 $H,M,L_i$ 中的子树。

时间复杂度 $\Theta(n \log n)$

Problem 2

平方运算相当于指数乘二，因此其循环节长度的 $\operatorname{lcm}$ 为 $2^x \pmod {998244352}$ 的循环节长度。

$998244352=7\times 17 \times 2^{23}$，其循环节长度应该很短，具体跑一下发现循环节长度为 $24$。

使用线段树维护，对于一个 $a_i$，如果它当前不在循环节上（$a_i$ 的变化可能是 $\rho$ 型的），那么可以暴力修改。

否则线段树上每个区间维护一个长为 $24$ 的环，每次平方就将环往前转一格即可。复杂度 $\Theta(cq log n)$，其中 $c=24$。

Problem 3

利用给定条件不难求出树的质心 $c$（可以将每条边看做质量在中点处然后求加权平均），转动惯量 $I$（中点距离质心 $d$ ，长度 $l$ 的边的转动惯量为 $I=\frac{1}{12}\eta l^3 + \eta ld^2$ ，然后对所有边求和）和外力矩 $M$ （设质心到边中点矢量为 $r$，则这条边的力矩为 $r \times f_i$，其中为 $\times$ 向量外积，然后对所有边求和），并求出角加速度 $\beta=M/I$，进而得到初始角度 $\theta=\frac{1}{2}\beta t^2$ 和角初速度 $\omega=-\beta t$，并得到时刻 $T$ 的角度 $\theta_T = \frac{1}{2}\beta(t-T)^2$。

对于树质心的运动，求出结束时加速度 $a_t = F_t/M = r(\cos \theta, \sin \theta)$，则时刻 $T$ 的加速度为 $a_T = r(\cos(\theta + \frac{1}{2} \beta(t-T)^2), \sin(\theta + \frac 12 \beta(t-T)^2))$，由于初始时质心速度为 $0$ ，则质心在这段时间的位移量为：

$$\int_0^t \int_0^x a_T \mathrm d T \mathrm dx = -\frac 12 \int_{t^2}^0 r(\cos(\theta+\frac 12\beta\alpha), \sin(\theta+\frac 12\beta\alpha)) \mathrm d\alpha$$

最后的积分根据 $\beta$ 是否为 $0$ 讨论后可以求出。

于是问题得到了解决，时间复杂度 $\Theta(n)$。

Problem 4

容易将问题分成两个部分：第一部分找出 $A$ 的数的集合，而第二部分找出 $A$ 的顺序。考虑到给出的次数限制，平均每一次询问我们需要利用到超过一位的信息，首先考虑找出集合的部分，我们可以将每个数标为 $0$ 或 $1$，那么每次操作即是求不超过 $M$ 个数之和。

考虑一个经典问题，给定 $L$ 个数构成的 $0/1$ 串，如何通过查询子集和确定该串中每个位置的取值，朴素的解法需要查询线性次，而实际上我们可以构造出查询 $O(\frac{L}{\log L})$ 次的方法：不妨假设我们能用 $a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $b$ 的序列的取值，我们就可以用 $2a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $2b + a − 1$ 的序列的取值。

这是通过先查询前 $b$ 个数的和 $s$，随后对于每一个用来查询长度为 $b$ 的序列的询问，不妨假设其在前 $b$ 个位置的和为 $u$，接下来的 $b$ 个位置和为 $v$，我们分别查询 $s - u + v$ 和 $u + v$，容易发现此时我们在第二次询问中还可以额外多查询一个位置的值，仍然可以还原 $u$ 和 $v$，因此我们就可以多询问出 $a - 1$ 个位置的值了，这样递推下去便是一个 $O(\frac{L}{\log L})$ 次查询的方法。而对于任意长的给定序列，我们可以将其拆成若干小段来进一步减少所需的次数。在本题中，有一个分值较大的测试点便是给这一部分解法（第二部分采取暴力方法）。

经过思考可以看出，当前问题下的最本质不同是一个随机位置是 $0$ 和 $1$ 的概率是不同的，因此直接采取上述方法会浪费许多次数。

然而，如果我们能够将长度为 $N$ 的序列切成若干段，每段恰包含一个 $1$，那么每一段中随机选一个子集值为 $0$ 和 $1$ 的概率就均等了，而我们一开始随机均等划分每个长度为 $M$ 的段只需要 $O(N/M)$ （期望情况下常数在 2.3 以内）次即可得到若干这样的段。在朴素的情况下，我们对于每一段都需要二分。然而实际上，由于每一段二分时概率均等，我们可以利用经典的求 $0/1$ 序列方法进行优化，即对二分的过程进行并行。经过简单分析，这样可以在这一部分做到 $M \log \log M$ 级别的询问次数。在这一部分，还有一个小的常数优化是我们可以每次选择长度不超过 $2M$ 的序列，在每次询问时只需询问元素个数较小的一侧即可（我们总要询问总和）。

有了以上铺垫，第二部分也可以用 $M \log \log M$ 次询问次数解决了：对于第二部分，我们可以一层层二分每个元素对应的位置，每次将所有可能的位置减半填上该元素。由于每个位置对应恰好一个元素，在每一层我们总能用元素将询问的位置填满，这样在自上至下的第 $i$ 层就是询问长度为 $2^i$ 的 $0/1$ 序列的元素值。略微精细的实现有助于减少最终所需的询问次数。