相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3514
神犇题解：http://www.cnblogs.com/zhonghaoxi/p/3651591.html
解题报告
这是LCT的经典应用，我们把每条边的权值设为它的编号
然后用LCT动态维护最大生成树
同时记录第$i$条边加入时取代的那一条边的编号$a_i$
对于询问，我们发现对于询问$[l,r]$
只有$a_i < l$的边才会使连通块的大小减少$1$
于是问题变为询问一个区间内小于某个数的个数
这是又是函数式线段树的经典应用
于是这题用LCT和函数式线段树就可以解决
时间复杂度：$O(n \log n)$
相关拓展
这题还可以很方便地将问题改为删掉$[l,r]$的边之后连通块的个数
这个我们将序列倍长，然后直接转化为原问题
I have been exploring for a little for any high quality articles or blog posts on this kind of area . Exploring in Yahoo I ultimately stumbled upon this web site. Reading this info So i¦m glad to exhibit that I have a very just right uncanny feeling I came upon exactly what I needed. I most without a doubt will make certain to don¦t overlook this website and provides it a glance on a constant basis.
Normally I do not read post on blogs, but I would like to say that this write-up very forced me to try and do so! Your writing style has been surprised me. Thanks, very nice article.