A
数学题，不会。
随便取一数 \(v\)，询问得到 \(t \equiv \log_g v \pmod p\)。
我们希望找到 \(x\) 使得 \(v^x \equiv g \pmod p\)，即 \(g^{tx} \equiv g \pmod p \Leftrightarrow tx \equiv 1 \pmod {p-1}\)。那么只要 \(t\) 与 \(p - 1\) 互质即可求得逆元。
有原根相关知识可以知道 \(v\) 是模 \(p\) 意义下的原根即满足上述条件，所以找到最小原根即可一次询问解决。
由于良心出题人没把询问次数卡太死，完全可以多随机几次直到 \(\gcd(t, p - 1) = 1\)。
B
战绩可查 17/0/0
C
考虑分治，找到一条边作为分治中心，将图分为两部分，跨左右的路径必定经过所选边的两个点。
从两个点出发跑 dij 算出到两边点的距离。对于一个点 \(u\)，设其到两端的最短路分别为 \(a_u, b_u\)，那么左右两点 \(u, v\) 的最短路为 \(\min(a_u + a_v, b_u + b_v)\)，从 \(a\) 走的分界是 \(a_u + a_v \le b_u + b_v \Rightarrow a_u - b_u \le b_v - a_v\)。排序后可以线性求跨分左右的路径对答案的贡献。
找分治中心可以直接枚举边，看两边点的数量...跑 dij 只需（也只能）求起点到当层点的最短路，但是子图信息可能不全不一定是原图最短路，但是不全的信息只是分治的另一半的信息，更改被选为分治中心的边权为两点的最短路即可解决。
然后过不了 \(\forall i\in[2, n], i\) 与 \(1\) 连边的特殊性质...但我场上代码过了，拼一下。
首先求 \(1\) 为起点最短路，然后有 \(1\) 的答案。
剩下的点要么经过 \(1\)，要么不经过 \(1\)，经过 \(1\) 的路径长为 \(dis_{1,x} + dis_{1,y}\)，不经过的是一段连续区间。
暴力枚举每个点不经过 \(1\) 的区间端点，条件是 \(dis_{1,x} + dis_{1,y} \ge dis_{x, y}\)（\(dis_{x, y}\) 显然可以前缀和求），然后过了...
数据水在了奇怪的地方。
标签：...,19,短路,分治,24.10,pmod,dis,equiv From： https://www.cnblogs.com/KinNa-Sky/p/18491546