A：

考虑随便取一个数 $v$，用一次询问问出 $t=\log_g v$。

我们希望找到一个 $x$ 使得 $v^x\equiv g\pmod p$，也即 $g^{tx}\equiv g\pmod p\iff tx\equiv 1\pmod {p-1}$。于是，我们希望找到的 $v$ 使得 $t$ 与 $p-1$ 互质即可。

由原根的相关知识我们知道，这样的 $v$ 就是 $\pmod p$ 意义下的原根。于是找到 $\pmod p$ 意义下的最小原根后，即可在一次询问内解决问题。

B：

没改。

C：

边分治。

假设我们现在钦定了一条边，那么这条边一定将图划分为两部分，而且从一部分中的点 $a$ 到另一部分中的点 $b$ 一定经过这条边的端点之一。

设两端点为 $l,r$，那么 $dis_{a,b}=\min(dis_{a,l}+dis_{l,b},dis_{a,r}+dis_{r,b})$，而 $a_u+a_v\le b_u+b_v\iff a_u-b_u\le b_v-a_v$，排一遍序即可统计跨过这条边的答案。

考虑每次找到左右两部分边数最接近的边，不断分治即可，时间复杂度为 $\mathcal O(n\log^2n)$。