This problem asks for the number of nodes not covered by any of the unioned subtrees after a sequence of operations. Each operation selects two nodes a and b, then marks all nodes in subtree(a) ∪ subtree(b). For each node v, we must compute how many operations affect it — i.e., how many times v appears in such unions — and finally output n − (number of operations covering v) − (whether v is directly activated by tree-difference marking).

The core challenge lies in efficiently maintaining per-node coverage counts under repeated interval-based updates on the DFS-order array, where each subtree corresponds to a contiguous segment.

Approach 1: Square Root Decomposition

We partition the DFS-order array into blocks of size ≈ √n. Each block tracks a frequency array for net insertions (offset from baseline), using short to conserve memory. A global offset per block avoids updating every element on range addition. Querying zero-counts reduces to summing block contributions where offset == 0.

Time: O(m√n), Space: O(n).

Approach 2: Segment Tree with Lazy Propagation (Zero-Centric)

Instead of tracking full frequencies, observe that only the count of zeros matters. We maintain a segment tree where each node stores:

• cnt: number of positions in its interval with value 0,
• lazy: total additive offset applied uniformly to the whole interval.

When propagating, if lazy > 0, then cnt = 0; otherwise, cnt aggregates children’s counts. Updates apply lazy tags; queries read root’s cnt.

Time: O(m log n), Space: O(n).

Approach 3: Segment Tree Tracking Minimum and Frequency

A more general but equally efficient variant maintains:

• min_val: minimum value in the interval,
• freq_min: how many times min_val occurs.

Since all updates are additive and non-negative (and removals exactly invert prior additions), min_val stays ≥ 0. A zero count exists iff min_val == 0, in which case answer is freq_min. Merging nodes compares minima and sums frequencies accordingly.

Time: O(m log n), Space: O(n).

Approach 4: Rollback-Aware Segment Tree

Leveraging the fact that all "deletions" reverse earlier "insertions", we implement a stack-based rollback mechanism. Before any update, affected nodes’ original states are saved. To undo, we restore those states in reverse order. This avoids persistent structures while supporting versioned semantics.

Time per operation: O(log n) amortized; worst-case space: O(m log n).

Implementation Notes

All methods begin by building the DFS order and computing subtree intervals. Tree-difference arrays record direct node activations (i.e., nodes whose own subtree was selected). Then, for each operation, we decompose subtree(a) ∪ subtree(b) into up to two disjoint DFS intervals — handling containment and disjoint cases separately — and schedule them as events at interval start/end positions.

Finally, scanning the DFS order from 1 to n, we apply scheduled updates, query current zero coverage, and compute answer as:
answer[node] = n − (zero_count) − (direct_activation_flag).