### Dec0Dedd's blog

By Dec0Dedd, history, 3 years ago,

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.

 » 3 years ago, # |   +1 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)$