第一场：

A：

首先去除所有未确定的叶子节点，然后计算每个结点的最终状态，若根节点不为零，则当前胜负状态已经确定，否则计算有哪些初始值为 0 的叶子节点，使得将他的状态定为 -2 后根节点状态为 -2。

直接递归求合法叶子节点即可，时间复杂度 $\mathcal O(n)$。

B：

先求出全源最短路。

然后我们来考虑原题中的式子，可以发现 $\mu_{\mathrm{s}, \mathrm{t}}(v)=\mu_{s, v} \cdot \mu_{v, t}$
如果此时 s 和 v 固定，那么我们得到了新的计算式子

$$R(v)=a_{s} \cdot \mu_{s, v} \sum_{t} \frac{a_{t}}{\mu_{s, t}} \cdot \mu_{v, t}$$

这样我们先枚举 s ，然后先按照拓扑序 dp ，求出形如 $(\mathrm{S} ,* )$ 的 $\boldsymbol{\mu}$ 值，然后再逆拓扑序做一遍 dp ，计算每个 v 值的贡献，最后枚举一遍 v 进行更新答案即可。
对于 $n=m-1$ 的情况：不用求最短路也不用拓扑 $dp$ 求 $\mu$ 值。
对于 $b_i=1$ 的情况：不用求最短路。
对于 $c_i=1$ 的情况： 不用求 $\mu$ 值。

C：

我们将询问按 $r$ 排序，每次动态加入一个点。

在线段树每个节点维护这一段的有序序列和这一段的答案。

考虑加入 $a[r]$ 时，会修改前面所有点作为左端点的答案，但是，我们发现，每个点作为左端点的答案，从左到右是递增的。否则，右边有一个更优的答案，查询的时候包含了右边，那么左边的答案事实上是没有用的。

所以记录当前的最小答案 $d$ ，先更新右边，再更新左边。

如果当前加入的数 $x$ 在这一段的前驱和后继与 $x$ 的差都大于等于 $d$ ，那么答案不优，结束更新。否则递归更新。

这样复杂度是有保证的，考虑最坏的情况是更新到了最左边的端点，那么序列应该是 $a[1]=1, a[2]=n, a[i]=(a[i-1]+a[1]) / 2-1$ 才会达到最坏情况，每次把值域减少一半，最多只有 $\log$ 次更新。

第二场：

A：

找到最大子段和与最小子段和，不难想到此区间内的该变量均合法。

B：

二分答案，对于 $a$ 的每一位都用 bitset 记录满足条件的序列，并起来为 1 的即是答案。

C：

防 AK的题。

Gale-Ryser 定理

剩下的就很简单了。

D：

原题

肖芬图题解。