P4350题解

· · 题解

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

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

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

num_{node}=n- \text{度数为0的点数}-\text{度数为2的点数}+\text{每一个点度数都为2的联通块数}

类似地，剩下的边数为

num_{edge}=m-\text{度数为2的点数}+\text{每一个点度数都为2的联通块数}

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