是一张由 个点和 条边组成的无向图。 中没有自环和重边。每条边有两种状态“开”和“关”。一开始,所有的边都是“关”着的。
现在有 个操作 ,表示将从 到 的最短路上的边改变状态(如果状态为“开”则变成“关”,反之,变成“开”)。如果 到 存在多条最短路,则我们选取点序列字典序最小的那一条。
比如,将所有从 到 的路径上的点表示成序列为 。那么我们从中取字典序最小的那一条。
在每一次操作后,你需要计算在图中由所有点和状态为“开”的边所组成图的连通块的数目。
Constraints
Solution
题目保证图是联通的,所以整个图为一棵环套树,去掉环之后则是森林。然后就可以 dfs 序链剖然后上线段树了,修改操作路径异或即可,其中环在线段树上要占用环大小的连续区间。
对于树来说,连通块个数即为点数 - 边数。询问时需要特判一下环上的情况,如果整个环都是开的,则 ans++ 。
Code
1 |
|