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!