题解链接

没有使用最短路算法，涉及一点点线段树标记永久化的思想。