P4350

Evan_Leo_Azir · 2025-10-10 20:55:59 · 题解

首先，边只有在其边权大于或等于优先级阈值 p 时，这条边才会出现，如果不对 p 进行些约束，其存在情况显然不好处理，所以将边与询问离线，排序，这样就可以据边权从大到小加边了。

接下来思考图转化的本质，发现每次操作分为两种情况。

一

点的度数为 0，直接删点，此时点数减一，边数不变。

二

点的度数为 2，且其不为自环，此时删去点及其连边，且连接之前与此被删去点相连的点，此时点数减一，边数减一。

考虑维护这两种操作的数量，以计算点数及边数。

发现，操作不会影响点的度数，且操作 1 的个数相对好处理，只需要记录度数为 0 的点即可，思考操作 2 ，注意到记录度数为 2 的点也很轻松，只需特殊解决自环的情况。

题目明确规定原图不会有自环，所以其只会后天生成，观察得，当一个联通块为环时，会经过若干轮的“操作二”，最终生成一个自环。所以得到如下式子。

设 a，b，分别为操作一，二的个数，cnt_x 为度数为 x 的点的个数，cyc 为环的个数，则：

当前的点数，边数也就极易求得了。

至于计算环的数量，可以使用并查集启发式合并，每次记录联通块中度数为 2 的点数及块的大小，当两者相等时，此联通块就是环

代码