ABC308Ex Make Q
有一种 \(O(n^4)\) 的思路，就是枚举度为 \(3\) 的那个点，假设是 \(u\)，再枚举环上与 \(u\) 相连的两个点 \(i\)、\(j\) 和与 \(u\) 相连的另一个点 \(k\)。我们只需再预处理出不包含 \(u\) 时 \(i\rightarrow j\) 的最短路 \(f[i][j]\)，那么当前的答案就是 \(dis[u][i]+dis[u][j]+dis[u][k]+f[i][j]\)，然后去 \(min\) 即可。
但是这样过不了。我们可以考虑分块，这样时间复杂度为 \(O(n^3\sqrt n)\)。