设 \(f_{l, r, p}\) 表示区间满足 \(\operatorname{argmax}\limits_{l \le i \le r} A_i = p\) 的情况下区间 \(\left[l, r\right]\) 的最大利益，有转移：
\[f_{l, r, p} = \max\limits_{l \le i \le p - 1}f_{l, p - 1, i} + \max\limits_{p + 1 \le i \le r}f_{p + 1, r} + \max\limits_{k}\left\{V_{p, k} \times \sum\limits_{l \le i \le p} \sum\limits_{p \le i \le r} Q_{i, j} - C_{p, k}\right\}
\]
注意到若对于 \(p, q\) 满足 \(l \le p, q \le r\) 且 \(A_{q} < A_{p}\)，那么一定有 \(f_{l, r, q} < f_{l, r, p}\)。即可以最优方案中的 \(p\) 一定是最大值，因此我们可以考虑设 \(f_{l, r}\) 表示区间 \(\left[l, r\right]\) 的最大利益，转移时枚举最大值，有：
\[f_{l, r} = \max\limits_{l \le p \le r}\left\{f_{l, p - 1} + f_{p + 1, r} + \max\limits_{k}\left\{V_{p, k} \times \sum\limits_{l \le i \le p} \sum\limits_{p \le i \le r} Q_{i, j} - C_{p, k}\right\}\right\}
\]
发现转移式的后半部分可以写为斜率优化的形式，进而可以对于每个 \(p\) 建出凸包。
若直接在凸包上二分那么复杂度为 \(\mathcal{O}(n^3\sum\log k)\)，无法接受。
考虑通过改变转移顺序使得在凸包上查询的斜率递增，发现可以先逆序枚举 \(l\)，后正序枚举 \(p\)，最后正序枚举 \(r\)。时间复杂度为 \(\mathcal{O}(n^3 + n \sum k + \sum k \log k)\)，可以通过。
首先考虑如何计算根链期望长度 \(\operatorname{depth}_u\)，不难发现通过枚举其父亲节点可以得到转移式：
\[\operatorname{depth}_u = c_u + \sum\limits_{p < u} \dfrac{a_p}{s_{u - 1}} \times \left(\operatorname{depth}_p + c_p\right)
\]
其中 \(s_i = \sum\limits_{j \le i} a_j\)，即 \(a\) 的前缀和。不难发现通过维护 \(\sum\limits_{p < u}{a_p} \times \left(\operatorname{depth}_p + c_p\right)\) 的值可以在 \(\mathcal{O}(1)\) 的时间内计算出 \(\operatorname{depth}_u\)。进而我们可以在 \(\mathcal{O}(n)\) 的时间内计算出所有节点的 \(\operatorname{depth}\)。
考虑如何计算点对 \(u, v\) 间的期望距离，不难发现可以通过枚举其最近公共祖先 \(x\) 得到转移式（假设 \(u < v\)）：
\[\begin{aligned}
\operatorname{dist}(u, v) &= \sum\limits_{x \le u} \operatorname{P}(x) \times \left(\operatorname{depth}_u + \operatorname{depth}_v - 2 \cdot \operatorname{depth}_x\right) \\
&= \operatorname{depth}_u + \operatorname{depth}_v - 2 \cdot \sum\limits_{x < u} \operatorname{P}(x) \times \operatorname{depth}_x - 2 \cdot \operatorname{P}(u) \times \operatorname{depth}_u \\
\end{aligned}\]
首先考虑如何计算 \(\operatorname{P}(u)\)，发现其等同于 \(u\) 在 \(v\) 的根链上的概率，不妨假设路径 \(u \rightarrow v\) 上的节点依次为 \(k_1, k_2,\cdots, k_l\)，那么这条路径出现的概率为：
\[\begin{aligned}
&\dfrac{a_u}{s_{k_1 - 1}} \times \dfrac{a_{k_1}}{s_{k_2 - 1}} \times \cdot \times \dfrac{a_{k_l}}{s_{v - 1}}\\
=&\dfrac{a_u}{s_{v - 1}} \times \prod\limits_{1 \le i \le l} \dfrac{a_{k_i}}{s_{k_i - 1}}
\end{aligned}\]
可以发现 \(\operatorname{P}(u)\) 即为 \(u, v\) 之间所有可能的路径的概率之和，因此有：
\[\begin{aligned}
\operatorname{P}(u) &= \sum\limits_{u < k_1 < k_2 < \cdots < k_n < v} \dfrac{a_u}{s_{v - 1}} \times \prod\limits_{1 \le i \le l} \dfrac{a_{k_i}}{s_{k_i - 1}} \\
&= \dfrac{a_u}{s_{v - 1}} \times \sum\limits_{u < k_1 < k_2 < \cdots < k_n < v} \prod\limits_{1 \le i \le l} \dfrac{a_{k_i}}{s_{k_i - 1}} \\
&= \dfrac{a_u}{s_{v - 1}} \prod\limits_{u < i < v}\left(1 + \dfrac{a_{i}}{s_{i - 1}}\right) \\
&= \dfrac{a_u}{s_{v - 1}} \prod\limits_{u < i < v}\dfrac{a_{i} + s_{i - 1}}{s_{i - 1}} \\
&= \dfrac{a_u}{s_{v - 1}} \prod\limits_{u < i < v}\dfrac{s_i}{s_{i - 1}} \\
&= \dfrac{a_u}{s_u}
\end{aligned}\]
继续考虑对于 \(x < u\)，如何计算 \(\operatorname{P}(x)\)，不妨将点分为两部分，第一部分为标号在 \(\left(x, u\right)\) 之间的点，第二部分为标号在 \(\left(u, v\right)\) 之间的点。
对于第一部分的点，其可能的出现情况为：
- 不在路径中出现
- 仅在路径 \(x \rightarrow v\) 中出现
- 仅在路径 \(x \rightarrow u\) 中出现
对于第二部分的点，其可能的出现情况为：
- 不在路径中出现
- 仅在路径 \(x \rightarrow v\) 中出现
因此有：
\[\begin{aligned}
\operatorname{P}(x) &= \dfrac{a_x}{s_{u - 1}} \times \dfrac{a_x}{s_{v - 1}} \times \prod\limits_{x < i < u} \left(1 + \dfrac{a_i}{s_{i - 1}} + \dfrac{a_i}{s_{i - 1}}\right) \times \prod\limits_{u < i < v} \left(1 + \dfrac{a_i}{s_{i - 1}}\right) \\
&= \dfrac{a_x^2}{s_{u - 1} \times s_{v - 1}} \times \prod\limits_{x < i < u}\dfrac{2 \cdot a_i + s_{i - 1}}{s_{i - 1}} \times \prod\limits_{u < i < v}\dfrac{a_i + s_{i - 1}}{s_{i - 1}} \\
&= \dfrac{a_x^2}{s_{u - 1} \times s_{v - 1}} \times \prod\limits_{x < i < u}\dfrac{2 \cdot a_i + s_{i - 1}}{s_{i - 1}} \times \prod\limits_{u < i < v}\dfrac{s_{i}}{s_{i - 1}} \\
&= \dfrac{a_x^2}{s_{u - 1} \times s_{u}} \times \prod\limits_{x < i < u}\dfrac{2 \cdot a_i + s_{i - 1}}{s_{i - 1}} \\
\end{aligned}\]
可以发现该式仅与 \(u\) 有关，因此可以快速计算。
总复杂度为 \(\mathcal{O}(n \times f(p) + q)\)，其中 \(f(p)\) 表示计算某数在模 \(p\) 意义下的逆元的复杂度。