Expected Connected Components on a Randomized Tree Road Network

Klee lives on a rooted tree whose nodes are initially numbered from $1$ to $n$. To facilitate her travels, the people of Mondstadt plan to build a new road from every non‐leaf node. In particular, for each non‐leaf node $u$ (with respect to the current root), one child $v$ is chosen uniformly at random and a new road is built between $u$ and $v$. These newly built roads form a forest (each component is a tree). You are asked to report the expected number of connected components in this random road network. A key observation is that if the current tree (with a designated root) has $L$ leaves (in the rooted sense), then one can prove that the random process always produces a forest with exactly $L$ connected components – and thus the expected number is exactly $L$.

However, Klee thinks this is too easy. She further introduces dynamic modifications to the tree. There are three types of operations on the tree (the operations occur sequentially and affect subsequent operations):

• Add u: Add a new node as a child of node $u$. The new node’s label is $n+i$, where $i$ is the (1-indexed) overall operation number. It is guaranteed that node $u$ exists.
• Del u: Delete node $u$. It is guaranteed that node $u$ exists and is a leaf. Also, the tree will never become empty.
• Upd u: Change the designated root of the tree to node $u$. It is guaranteed that node $u$ exists.

For the initial tree and after each modification, report the expected number of connected components, which, as argued above, is equal to the number of leaves in the tree when viewed as a rooted tree.

Note on the leaf count: In an undirected tree, a vertex is considered a leaf if its degree is $1$. However, when the tree has only one vertex, that vertex is considered a leaf. When the designated root is a leaf in the undirected sense (i.e. its degree is $1$ and the tree has at least $2$ nodes), then after re-rooting the new root is not counted as a leaf in the rooted tree (because it always has at least one child). Thus, if $T$ has at least $2$ nodes and the current designated root $r$ has degree $1$, then the answer is
\[ \text{answer} = (\#\text{ of leaves in the undirected tree}) - 1. \] Otherwise, the answer is simply the number of leaves in the undirected tree.

Input Format:
The first line contains two integers $n$ and $m$, representing the number of nodes in the initial tree and the number of operations, respectively.
The next $n-1$ lines each contain two integers $u$ and $v$, representing an undirected edge of the initial tree. The tree is rooted at node $1$ initially.
The following $m$ lines each contain an operation in one of the following forms:

• Add u
• Del u
• Upd u

Output Format:
Output $m+1$ lines. The first line is the answer on the initial tree, and each of the next $m$ lines is the answer after performing the corresponding operation. Each answer is an integer representing the expected (and in fact, deterministic) number of connected components.

Explanation:
For example, consider the initial tree with 3 nodes and edges
    1--2, 1--3.
Here, the undirected leaves are nodes $2$ and $3$. With the root $1$, the leaves of the rooted tree are exactly the undirected leaves (node $1$ is not a leaf) and the answer is $2$. If an update changes the root to node $2$ (which is an undirected leaf), then node $2$ will have a child, and the new leaves become only one of the original leaves, so the answer becomes $1$.

Constraints: It is guaranteed that all operations are valid and the tree is never empty at any time.

inputFormat

The input begins with two integers $n$ and $m$ ($1 \le n, m \le 10^5$), representing the number of nodes and the number of operations respectively. The next $n-1$ lines each contain two integers $u$ and $v$ representing an edge in the undirected initial tree. The tree is initially rooted at node $1$. Then follow $m$ lines, each describing one operation in one of the following forms:

• Add u: add a new node as a child of $u$ (the new node’s label is $n+i$ for the $i$-th operation).
• Del u: delete node $u$ (it is guaranteed to be a leaf).
• Upd u: update the designated root to $u$.

outputFormat

Print $m+1$ lines, where the first line is the expected number of connected components (which equals the number of leaves in the rooted tree) for the initial tree, and each subsequent line is the answer after performing the corresponding operation.

sample

3 3
1 2
1 3
Upd 2
Add 2
Del 3

2
1
2
2

</p>