A. Add One

考虑把 $+1$ 看成 $xor a$ 操作，可以发现 $a$ 只可能是 $2^k-1 (k \ge 1)$。因此考虑枚举 $a$ 判断是造出来 $???????01111$ 的形式，可以从低位到高位建线性基，每次从低位到高位贪心的xor，时间复杂度 $O(n \log w)$

B. Beautiful Sum

$$ \sum_{i=1}^n (\mu(i)\mu(i+k))^2 \\ = \sum_{i=1}^n \sum_{d^2 | i} \mu(d) \sum_{e^2 | i+k}\mu(e) \\ = \sum_{d = 1}^{\sqrt n}\mu(d)\sum_{e=1}^{\sqrt n} \sum_{i=1}^n [d^2 | i \land e^2 |i + k] $$

最后一部分等价于 $ye^2-xd^2=k, 1 \le xd^2 \le n$ 的解的数量。可以利用 exgcd 计算。 同时也可以找到所有 $xd^2, ye^2$，用双指针计算所有相差为 $k$ 的数量。 因此可以对于 $d^2,e^2>B$ 的数对采用做法2，时间复杂度为 $\sum_{i=B}^{\sqrt{n}} \frac{n}{i^2} = \frac{n}{B}$，其它采用第一个做时间复杂度为 $O(B\sqrt{n} \log n)$， 令 $B = \frac{n^{1/4}}{\log^{1/2}} n$，时间复杂度为 $O(n^{3/4}\log^{1/2} n)$。

C. Counting Sequence

令 $B = \sqrt{2n}$。 当 $a_1 \le B$ 时$\max a_i$ 是 $O(\sqrt{n})$ 的，因此可以$f_{i,j}$ 表示和为 $i$ 上一个数字为 $j$。 当 $a_1 > B$ 时不需要考虑 $a_i>0$ 的限制，因此可以 $g_{i,j}$ 表示 $i$ 个数字，$\sum_{k=1}^i a_k-i\times a_1 = j$，考虑枚举 $a_1,a_2$ 的关系转移。 时间复杂度是 $O(n\sqrt{n})$。

E. Exciting Travel

原问题等价于，用 $p_i,p_{i+1}$ 的路径上的点换答案$+1$。 考虑建立虚树，令 $f_u$ 表示 $u$ 的子树的答案。对于$l_i = lca(p_i, p_{i+1})$，在$lca$ 处枚举是否选择这条路径。考虑所有的转移类似于$\sum_{u \in path(p_i,p_{i+1}), v\not \in path(p_i,p_{i+1})} f_v + 1$。考虑令 $g_u = \sum_{v} f_v-f_u$，这个式子可以写成$g$ 的链和加上常数的形式，因此在$dp$的过程直接维护$g$的前缀和即可。

F. Flower's Land

考虑点分治，分治重心为 $rt$，计算必须包含 $rt,u$ 的大小为 $k$ 的连通块的最大权值。 令 $f_{i,j}$ 表示先序遍历为 $[i,n]$ 内部的点选了 $j$ 个并且满足不存在 $u,fa_u$ 的 dfn序在$[i,n]$ 并且 $u$ 选了，$fa_u$ 没选，枚举是否选 $u$ 以此决定是否跳过 $u$ 的子树即可。类似的令 $g_{i,j}$ 表示后序遍历 $[1,n]$ 的选 $j$ 的权值。$O(k)$ 合并两个背包的某个点即可。 点分治的当前区域大小少于$k$ 的时候剪枝，复杂度为 $O(nk\log {\frac{n}{k}})$

G. Games

令 $f_{u,i,0/1}$ 表示 $u$ 的子树，$a_u = i$，是否有子树内的点比$a_u$ 大，利用前缀和转移即可。 类似的，令 $g_{u,i,0/1}$ 表示 $u$ 的子树补的答案。通过换根 dp 转移即可。时间复杂度 $O(nm+q)$。

I. Inverse Line Graph

考虑问题转化为，给新图每个点赋两个权值，代表的含义是原图的端点，因此需要保证任意一个颜色的导出子图是完全图，并且每条边在恰好一个完全图里，称边被颜色覆盖为边在这个颜色的导出子图里。 我们随便选一个点 $u$ 考虑把 $u$ 的出边划分成两个集合，分别代表两个颜色。不妨设 $u$ 的出度为 $S$，两种颜色的集合分别为 $S_1, S_2$。 假设我们得到了正确的划分，对于 $S$ 中的每个点，已经使用了一种颜色，对于剩下的没有被覆盖的边，必须成为一个新的完全图，因此可以递归处理。 设$x\in S_1, y_1,y_2 \in S_2$ 且 $(x,y_1),(x,y_2)$，那么 $x,y_1$ 和 $x,y_2$ 必须染一个颜色，但是 $y_1,y_2$ 的边已经被覆盖，因此无解。因此 $S_1,S_2$ 之间是一个匹配。 任选一个 $p \in S$，令 $S_1= \{p\}, S_2 = S - S_1$，并且检验一遍。 那么一定存在$p,q \in S_1, (p,q)$。假设我们有 $p,q \in S_1$ 的初始条件，那么对于$x \in S$，若与$p,q$ 均有连边，必须在$S_1$ 里，否则在$S_2$ 里。经过上述过程，假设 $p,q,t\in S$，那么 $p,q$ 在一个集合里与 $p,t$ 在一个集合里的初始条件是等价。对于 $t\in S_2,(p,t)$，通过上述方法同样检验一遍。如果仍然不满足意味着， $p,q$ 不在一个集合, $p,t$ 不在一个集合，因为 $t \in S_2$，所以 $t,p$ 没有边因此 $t,q$ 不在一个集合，于是无解。 因此可以转化为最多 $3$ 次检验，每次时间复杂度 $O(n+m)$，总时间复杂度$O(\sum n+\sum m)$。

J. Just Another Number Theory Problem

考虑计算 $s_i$ 表示有多少对相邻的差为 $i$，并且依次加入质数。 因为是任意两个数字互质，因此是均匀分布的，所以有转移$s_i:=(p - i + 1) s_i + 2 \sum_{j > i} s_j$，利用后缀优化即可。

N. No!

只用关心 $h$ 为前缀最大值的位置，因此对强按照从大到小排序后，令 $f_i$ 表示必须选第 $i$ 面强，不考虑第 $i$ 会倒的答案。那么有$f_i = \max_{j=1}^{i-1} \min(f_j, \frac{h_j-h_i}{a_j})$，后半部分可以看成一个平移的反比例函数和一个值域上限。因为对于两个 $j_1,j_2$ 对后续的贡献不考虑上限只有一个交点，因此考虑用类似于斜率优化的方式维护即可。如果使用基数排序和gcd技巧可以做到 $O(n + m + q)$。