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](https://en.wikipedia.org/wiki/Dynamic_connectivity), but I'm not sure how to connect that problem to mine.↵
↵
Thanks in advance!
↵
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](https://en.wikipedia.org/wiki/Dynamic_connectivity), but I'm not sure how to connect that problem to mine.↵
↵
Thanks in advance!
