考虑每个铁路拆除造成的影响.
如果在开始或者结束,如果旁边的铁轨被拆除,连续段数-1,否则无影响.
如果不在开始结尾.
如果两边都被拆了,连续段数-1
如果一边被拆了,不变.
两边都没被拆,答案+1.
当然直接线段树做也是没有问题的.
题意转换,出发 中专点 结束 路径max变为出发 中转点 or 出发 结束 路径max
路径max考虑克鲁斯卡尔重构树.
没有修改的答案显然初始是很好算的.
然后考虑每个点的修改.对于每个点,求出来它作为空地的贡献和作为城市的贡献,然后每次依次考虑贡献对答案的影响即可.
自行阅读我题解博客推导即可.