考虑怎么较容易地表示 \(\operatorname{dist}(u,v)\)。注意到对于每个点 \(v\)，\(\leq 1\) 步能到 \(v\) 的点形成一段区间，记为 \([l_v,r_v]\)。考虑枚举终点 \(x\) 和最短路长度 \(d\)，动态维护所有 \(\operatorname{dist}(u,v)\leq d\) 的所有点 \(u\)，这些 \(u\) 显然也是一段区间，记为 \([L,R]\)。答案即为对于每个时刻 \(n-(R-L+1)\) 的和。
可以发现，当 \(d\leftarrow d+1\) 时，区间 \([L,R]\) 会变为 \([\min\limits_{i=L}^Rl_i,\max\limits_{i=L}^Rr_i]\)，这就是和 CF1707E 一样的形式。但是此时还需统计长度和，不能用 CF1707E 的方法直接做。
观察所有区间 \([l_i,r_i]\) 的性质，事实上 \([L,R]\) 的 \(\min l\) 只和 \(L\) 和 \([L,R]\) 中出现的字符有关，\(\max r\) 同理。于是每次只需要找到第一次出现新的字符的时刻就好了，因为对于每个 \(L\) 和 每个 \(R\)，不同的字符集合只有 \(\leq|\Sigma|\) 个，直接预处理跳一步之后的位置，倍增即可。
时间复杂度为 \(O(n|\Sigma|\log n)\)，空间可以通过每次统一处字符集大小相同的区间做到 \(n\log n+n|\Sigma|\)。
https://codeforces.com/contest/1246/submission/284135674
标签：字符,dist,log,CF1246F,leq,区间,Sigma From： https://www.cnblogs.com/cjoierzdc/p/18445763