A：

学生大战一个半小时未果，结束前半小时发现是打表找规律。

就是分讨一下，首先大于 $1$ 的数不能超过两个，若有两个则其中一个必定为 $2$，然后看一下 $1$ 的个数是不是 $3$ 的倍数即可。

B：

拆贡献，分为 $u\rightarrow lca$ 和 $lca\rightarrow v$，前者需要求出 $S[1, i]$ 作为子序列出现了多少次，后者需要求出 $S[i, |S|]$ 作为子序列出现了多少次，两者是对称的。

对于每个 $u$，求出 $u$ 到根的路径上有多少个子序列为 $S[l, r]$，记为 $f_{u, l, r}$，这个数组容易在 $O(n |S|^2)$ 内的时间预处理。

查询时考虑 $f_{u, 1, i}$ 代表的 $S[1, i]$ 在 $u$ 到 $lca$ 和 $lca$ 父亲到根两条路径之间的分布，比如 $u$ 到 $lca$ 上有 $S[1, j]$ ，$lca$ 父亲到根有 $S[j+ 1, i]$，后者预处理时已经被求出来了，因此可以容斥掉这部分贡献，总时间复杂度 $\mathcal O(n \log n + (n + q) |S|^2)$。

C：

启发式分治，每次找到区间最大值 $i$，那么区间内包含 $i$ 的合法区间不超过 $\log$ 个，然后每次选择 $i$ 左右两侧较短的一侧，枚举区间和，判断另一端点是否在区间内，直接转移即可。

需要一开始将所有前缀和塞到 $map$，不能分治时现塞，因为区间长度无法保证。

D：

无法战胜。