DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

DOM Tree

Back to problem

Editorial

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

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

When entering node vvv, 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)(v,1)(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)(v,1)(v,1) is processed, append the closing tag.

Let SSS be the sum of the numbers of nodes over all test cases and let LLL 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)O(S+L)O(S+L). The memory usage for one test case is O(N+L)O(N+L)O(N+.

Solution written by GPT5.6

L
)