树的路径变换问题

最后一条操作的路径长度一定为 \(1\)，在断开它之前它联通的两个连通块中的操作必须被全部完成。

那么可以倒序模拟操作：将 \(2n-2\) 条输入的边一起维护，如果两个点之间有两条边以上就把其中一个删掉，在它边表里面的边连到另一个点上。如果可以删到只剩下一个点，那么存在操作序列

为保证复杂度，需要删掉度数较小的点。使用 unordered_map 维护某条边的出现次数，set 维护邻接表。时间复杂度 \(\Theta(n\log^2 n)\)

相似序列问题

稀疏阶乘问题

\(m|f(x)\Rightarrow m|f(x+m)\) 设 \(M(x,z)\) 表示最小的 \(v\) 使得 \(v\equiv z(\bmod x),x|f(v)\)

求出来 \(f(m,z)\) 后本题可以 \(\Theta(1)\) 找到每个余数有几个范围内的数字来统计答案。

将 \(m\) 质因数分解为 \(\displaystyle\prod p_i^{e_i}\)，注意到 \(x\perp y\) 时，\(M(xy,z)=\max(M(x,z),M(y,z))\) 所以求出来 \(M(p_i^{e_i},0\sim m)\) 即可

如果某个 \(e_i=1\)，那么此时任务为找到一个 \(j\) 满足 \(x\equiv j^2\mod p_i\) ，对于每个 \(p\) 求 \([0,m)\) 中每个余数的得数，可以枚举余数作为二次剩余的底数，可以更新的元素参考 \(50\) 分暴力。

当 \(e_i>1\) 时由于 \(v 的 \(v\) 就可以一定可以实现整除，枚举 \(v\in[0,p_ie_i)\) 来模拟即可，每个 \(k\in[0,m)\) 在每个 \(p_i\) 会被枚举 \(e_i\) 次，总复杂度 \(\Theta(m\log m)\)