本题使用树剖、$ST$ 表、最短路、倍增等，码量100多行，建议评紫。