Hey, I have a problem and I cannot think of any faster soltuion than $$$O(nm)$$$.
I'm given a tree with $$$n$$$ vertices and $$$n-1$$$ undirected edges. I'm also given $$$m$$$ queries ($$$m \le 10^5$$$) and each of them is an integer $$$x$$$ ($$$1 \le \lvert x \rvert \le n$$$). If $$$x > 0$$$ then we need to remove vertex $$$x$$$ from a tree and print number of connected components in that tree, otherwise if $$$x < 0$$$ then we need to add vertex $$$x$$$ to that tree (and also print number of connected components). Input data is correct i.e. no vertex will be added before it was removed.
What I thought of, was storing degree of each vertex. Then, if vertex $$$v$$$ was removed then number of connected components increases by $$$deg(v)-1$$$, but this way we also need to decrement by one degrees of vertices with edge with $$$v$$$ which can take $$$O(n)$$$ and that leads to $$$O(nm)$$$. Another idea, was to try to solve the problem using dynamic connectivity, but I'm not sure how to connect that problem to mine.
Thanks in advance!
Auto comment: topic has been updated by Dec0Dedd (previous revision, new revision, compare).
Removing a vertex has the same effect as cutting all of its existing edges. Then the answer would just be the number of cut edges + 1, minus the number of removed nodes.
Lets root the tree. Then, every removal will be cutting the edges to the node's children, and also cutting the edge to its parent (if it exists). We can do this quickly by using the BFS ordering of the tree. This is useful because a node's children will be a contiguous subsequence in the ordering. If we store the value of an element as the number of times its edge to its parent has been cut, we can update all the children with a range increment. This can be done with a segment tree. Then, the number of cut edges would be the number of positive values in the segment tree. Adding a node is just doing the same thing but doing decrements instead of increments.
This should take $$$O(m log n)$$$
This is a very good and easy solution , how can we extend this to a graph instead of a tree ?
It can be easily solved using DSU. Read all queries and go from last to first adding vertexes. It is obvious that we know number of components in DSU after any operation
Dsu works when only addition of edges is there ,but how to handle removal of edges?
Change removal to adding. If you have a query to remove an edge/vertex, firstly remove them all. Then go from last query to first adding vertexes.
It seems you didn't understand the problem correctly. There are both addition and deletion operations. And with dsu you can do only one type at once.
Ooops, sorry, definitely this problem cannot be solved using DSU.
is there any way to solve this where we have both addition and removal or edges ?
What do you mean by add vertex? Do we know if the vertex is connected to another node?
when you delete a vertex, is it deleted for future queries? So are we maintaining a forest?
Is there a problem link? That may be more clear.