DOM Tree

The HTML representation can be constructed by following the definition with a DFS. However, the tree depth can be as large as $N$, so an explicit stack avoids recursion-depth problems under the full constraints.

Store events $(v,\mathrm{state})$ in the stack. Let $\mathrm{state}=0$ mean entering a node for the first time, and let $\mathrm{state}=1$ mean leaving a tag node after all of its children have been processed.

When entering node $v$, process it as follows.

• If it is a text node, append its string directly.
• If it is a tag node, append its opening tag, push $(v,1)$, and then push its children in reverse order.

Because a stack processes the most recently pushed event first, pushing the children in reverse order makes the actual traversal follow the child order given in the input. When event $(v,1)$ is processed, append the closing tag.

Let $S$ be the sum of the numbers of nodes over all test cases and let $L$ be the total output length. Every node and every output character is processed only a constant number of times, so the time complexity is $O(S+L)$. The memory usage for one test case is $O(N+L)$.

Solution written by GPT5.6