A

算法 1

对于每组询问，暴力的算出每个二次函数的取值。

时间复杂度 $O(nq)$。期望得分 $20$ 分。

算法 2

当 $x>0$ 时，要求 $a_ix^2+b_ix$ 的最大值，只需要求出 $a_ix+b_i$ 的最大值。 于是问题就转化为了，给定一堆直线，求在某些点的最大值。显然答案一定在上凸壳上。 对于每组询问，只要二分出它在上凸壳的哪个位置就行。

同样的，当 $x<0$ 时，答案在 $a_ix+b_i$ 的下凸壳上，再写一个凸壳就行了。

时间复杂度 $O((n+q)\log n)$。期望得分 $100$ 分。

B

算法 1

直接按题意枚举，动态规划或是记忆化搜索。

时间复杂度 $O(a^n)$。期望得分 $30$ 分。

算法 2

考虑第二个测试点。只需要记录当前还有多少个位置为 $1$ 就行了。

时间复杂度 $O(n)$。期望得分 $10$ 分。加上算法 1，期望得分 $40$ 分。

算法 3

答案可以看成是每一个元素被选中的次数之和。由于期望的线性性，我们可以去计算每一个位置被选中的次数的期望。

首先，第一个元素一定被减了 $a_1$ 次。

考虑某一个位置 $i$，假设当前有 $c$ 个元素不为 $0$，那么每个元素被操作的概率都是 $\frac{1}{c}$。倘若只关注 $1$ 和 $i$ 两个元素，可以发现操作其它元素的时候对它们没有影响，而且它们两个被操作的概率是相等的。于是这个问题就等价与一个只有两个元素的原问题。

因此元素之间是独立的！使用算法 1 中的动态规划就可以知道每个元素对答案的贡献，求和即可。

时间复杂度 $O(a^2+n)$。期望得分 $60$ 分。

算法 4

算法 3 中的动态规划可以看成从 $(a_1, a_i)$ 出发的随机游走，每次随机一个方向将减 $1$，直到走到坐标轴上为止。若停在 $(0,a)$，对答案的贡献为 $a_i-a$。若停在 $(a,0)$，对答案的贡献为 $a_i$。

于是可以直接写出贡献的式子。

$$\sum_{i=0}^{a_i-1}i*\frac{a_1-1+i\choose i}{2^{a_1+i}}+a_i(1-\sum_{i=0}^{a_i-1}\frac{a_1-1+i\choose i}{2^{a_1+i}})$$

前面那项是停留在 $(0,a)$ 的答案，后面那项是停留在 $(a,0)$ 的答案。

当 $a_i$ 增加 $1$ 的时候，变化的贡献可以在 $O(1)$ 的时间内得到。（前后都是只增加了一项）

时间复杂度 $O(a+n)$。期望得分 $100$ 分。

C

算法 1

对于每组询问，遍历所有节点，看看它是不是在路径上，并计算答案。

时间复杂度 $O(nq)$。期望得分 $10$ 分。

算法 2

由于可能询问的点对只有 $O(n^2)$ 组，每次枚举 $u$ 开始深搜。

时间复杂度 $O(n^2)$。期望得分 $20$ 分。

算法 3

当树形态随机的时候，两个点之间期望只有 $O(\log n)$ 个点，暴力即可。

时间复杂度 $O(Hq)$。期望得分 $20$ 分，结合算法 2，期望得分 $30$ 分。

算法 4

当 $a_i<2$ 的时，按位或只会对最后一位产生影响，即，当 $dist(w,u)$ 为奇数且 $a_w=1$ 时，答案需要减 $1$。于是只要倍增时顺便维护从每一个点 $t$ 出发，向上 $2^i$ 的距离之内，与 $t$ 距离为奇数且点权为 $1$ 的点的个数就行了。

时间复杂度 $O(n\log n)$。期望得分 $10$ 分，结合算法 2、3，期望得分 $40$ 分。

算法 5

类似的，可以分别考虑每一个二进制位对答案的贡献。即，对于位 $2^x$，维护从每一个点 $t$ 出发，向上 $2^i$ 的距离之内，与 $t$ 距离为 $d$ 满足 $d \mathbin{\mathrm{and}} 2^x = 2^x$ 且点权的二进制表示中包含 $2^x$ 的点的个数就行了。

由于路径有向上的部分，也有向下的部分，因此还需要维护满足 $d \mathbin{\mathrm{and}} 2^x = 0$ 的点的个数在从 $v$ 倍增的时候使用。

时间复杂度 $O(n\log n \log a_i)$ 期望得分 $50$ ～ $60$ 分。

算法 6

注意到并不需要对于每一个位分别维护点的个数和，只需要维护所有重叠的位的数位和就行了，于是乎可以少掉一个 $\log$。

时间复杂度 $O(n\log n)$ 期望得分 $100$ 分。