即使没有人为你鼓掌，也要优雅的谢幕，感谢自己的认真付出。

[NEERC 2015] Distance on Triangulation

解释一下，这题哪里淀粉质了/fn。

首先先考虑一个暴力，即从每个点出发进行 $\text{BFS}$，复杂度应该是 $\mathcal{O}(n^2)$。

注意到这 $n-3$ 条边将原图分的死死的，互不交叉，故考虑能不能找到靠近中间的一条边拆成两半。

发现可以分治，即每次找到最中间的一条边，然后分成左右两半，跨过这条边的询问就可以通过 $\text{BFS}$ 得到答案。

时间复杂度 $\mathcal{O}(n\log n)$。