P4350题解

考虑将询问离线，按边权从大到小依次向途中加边。

如何计算当前的图经过一系列操作后的点数和边数？

注意到，操作（a）不影响任何其它点的点权；操作（b）同样不影响。所以图中度数为 $0$ 的点一定会被删去，不考虑自环，所有度数为 $2$ 的点也一定会被删去，其它点不会被删。考虑什么时候会形成自环，每一个没有其他分支的环，也就是每个点度数都为 $2$ 的环，会一直删点知道剩下编号最大的那一个。于是剩下的点数即为

类似地，剩下的边数为

每一个点度数都为2的联通块数可用并查集维护，具体地，维护一下每个并查集的点数以及度为 $2$ 的点数即可。