★ FEATURED ARTICLE 打开 UVa 11484 这道题的时候我第一反应是又一个模拟题结果做着做着发现事情没那么简单。题目名字叫 Document Object Model一上来就是网页前端的术语但剥开这层壳它其实是一道非常典型的文本解析 树结构 树上查询的综合题。你既要把一段类似 HTML 的文本正确解析成一棵 DOM 树又要在树上快速回答一堆关于包含关系的问题。这道题适合正在刷 UVa 老题的朋友、准备面试算法题的人以及所有想搞明白栈在解析里到底怎么用的初学者。我当年第一次提交就吃了个 TLE后来把递归改成迭代 DFS 才过这篇文章就把整个思路和踩坑过程完整讲清楚。1. UVa 11484 到底在考什么先看懂题再动手1.1 一道披着网页解析外衣的树上问题UVa 11484 给你的输入可以理解成一个简化版的 HTML 文档。里面有开标签比如html、body、p也有对应的闭标签/html、/body、/p标签内部可能还带属性比如a href...这种。文本内容在题目里通常是可以忽略的因为我们要关心的是结构不是文字本身。题目要求你把这个文档按照嵌套关系建成一棵 DOM 树。什么是 DOM 树就是每个标签是一个节点谁包含谁就是父子关系。html里套着body那 html 就是 body 的父节点body里套着p那 body 就是 p 的祖先。嵌套的深度决定了节点在树里的层次。然后是查询部分。这类题最常见的问法就是给你两个标签名问你第一个是不是第二个的祖先或者反过来也有的版本让你输出两个节点的深度差、兄弟关系、最近公共祖先之类的。UVa 11484 的原题在不同题库里描述略有出入但核心万变不离其宗你得先能建树再能高效回答树上关系。我第一次做这题的时候最大的困惑是这看起来就是个括号匹配凭什么单独出一道题后来想明白了括号匹配只是第一步建完树之后的查询才是真正的考点。如果每次查询都暴力向上爬父指针最坏情况下一个深链就把你打成 O(NQ)这么大的复杂度在 UVa 上不可能过。1.2 考察点拆解解析、建树、查询三件事拆开来看这题其实由三个独立的技术点组成任何一环掉链子都做不对。第一是解析。你要能从一长串字符串里分辨出开标签、闭标签、自闭合标签还要能把属性剥掉只留下标签名。这一步考的是对字符串处理的细致程度尤其要小心边界条件标签名空的、属性里又出现的、标签后面多一个空格之类的脏数据。第二是建树。解析过程中你要维护一个当前嵌套到哪一层的状态这天然就是栈的用武之地。遇到开标签就入栈遇到闭标签就出栈栈顶永远指向当前节点的父节点。这层逻辑不复杂但和你平时写的括号匹配有个重要区别括号匹配只需要计数器建树需要的是一棵真正的树所以每个标签都要分配一个节点 id并且记录它的父节点是谁。第三是查询。树建好了查询才能开始。如果题目只问A 是不是 B 的祖先你可以用 DFS 时间戳把判断变成两个整数的大小比较复杂度 O(1)。如果题目要你输出祖先和后代之间的深度差那你还要在 DFS 的时候顺便把每个节点的深度算出来。这三件事串起来才是这道题的完整解法。2. 整体设计为什么选栈 DFS 时间戳这套组合2.1 用栈维护嵌套关系标签匹配的最简方案很多初学者会想标签嵌套不就跟括号嵌套一样吗我用一个计数器不就行了这里有个关键差异标签是有名字的a必须由/a来关闭不能只看数量。而且标签还会重复出现比如一个页面里可能有十几个p你说栈顶弹出谁只能弹出最近入栈的那个。这就是栈的天然优势它维护的正是最近的未闭合标签这个状态。遇到div把它压栈现在我知道任何新解析到的标签父节点就是这个 div遇到/div弹出回到它外面的那层。整个过程就像你在编辑器里手动折叠代码块每次折叠到最里层展开也是从最里层开始。用生活里的例子更好理解你把一摞盘子一个个往上放收盘子的时候永远只能从最上面拿。标签的闭合顺序和打开顺序正好相反这就是后进先出栈是唯一不需要思考就能写对的数据结构。这里还要提一个工程上的细节HTML 标准其实允许标签不严格闭合比如br没有对应的/brp甚至可以自动闭合。但 UVa 这类刷题网站的题面通常给的是严格闭合的 XML 风格输入或者明确告诉你哪些标签可以自闭合所以我们可以用开标签压栈、闭标签弹栈的简单规则。做 ACM 题有一个原则按题面说话不要按真实世界的标准说话。真实 HTML 的容错规则极其复杂Tidy 库处理它都要写几万行题目给的一定是简化模型。2.2 DFS 时间戳如何用两个整数判断祖先关系树建好了怎么判断祖先关系最朴素的做法是从孩子节点开始沿着 parent 指针一路向上走看能不能碰到目标节点。这个方法在随机数据下可能表现还行但题目如果故意构造一条 10 万层的链子每次查询都走 O(N)直接超时。在竞赛题里判断树上祖先关系的标准做法是 DFS 时间戳也叫括号序或者进入时间 / 离开时间。你对树做一次深度优先遍历进入一个节点时记录一个时间戳 tin离开一个节点时记录另一个时间戳 tout。那么节点 u 是节点 v 的祖先当且仅当 tin[u] tin[v] 且 tout[v] tout[u]。这个性质用括号来理解最直观DFS 遍历的过程就像给整棵树套括号每个节点的子树就是一对完整的括号。u 是 v 的祖先说明 v 所在的整个子树包含在 u 的后代范围内也就是 v 的左右括号都落在 u 的左右括号内部。只要 tin 和 tout 满足包含关系祖先关系就铁定成立。我为什么偏爱这个方案因为它在 O(1) 时间内回答查询预处理只需要一次 O(N) 的 DFS。而且这个技巧在大量树上问题里都能复用比如最近公共祖先的 Tarjan 离线算法、树状数组维护子树权值、判断一个节点是否在另一条路径上全都建立在时间戳思想上。学会了它你买的不是一道题的答案是一套通用工具。2.3 复杂度分析为什么 O(N) 就能扛住全部查询把整道题的复杂度算一笔账解析阶段每个字符最多被扫描一遍遇到标签就做一次常数时间的入栈或出栈操作总计 O(L)L 是文档长度。DFS 预处理阶段每个节点进出一次总计 O(N)N 是节点数量。查询阶段如果每个查询用 O(1) 的时间戳比较配合哈希表把标签名映射到节点列表总复杂度就是 O(Q)。整体就是 O(L N Q)在 N 和 Q 都到十万级别的数据下跑起来毫无压力。对比一下暴力方案的复杂度解析同样是 O(L)但每次查询如果沿 parent 链向上找最坏 O(NQ)。同样是 10 万节点、10 万查询暴力是 10 亿次操作优化后是几十万次操作差距是三个数量级。UVa 的老题目虽然数据范围写在题面上但绝不会让暴力轻松过关这点我踩过太多次了。刷题的人一定要养成习惯动手写代码之前先算复杂度确认你的方案能跑在题目资源限制之内再开始敲键盘。3. 核心实现解析、预处理、查询的三段式代码3.1 解析器开标签、闭标签与属性剥离解析部分我建议把所有逻辑封装成一个函数输入是原始文档字符串输出是建好的树。为了便于处理我会在真正的文档根节点之上再建一个虚拟根节点名字叫#document。这样做的好处是文档如果只有一个根标签它也有一个确定的父节点就算输入格式比较松散多个顶层标签也能统一挂到虚拟根下面不会出现森林。扫描字符串的时候我只看和之间的内容。遇到就往后找到最近的中间的部分就是标签体。接下来做三件事判断是不是闭标签、剥离属性、判断是不是自闭合标签。判断闭标签非常简单看标签体的第一个字符是不是/。如果是说明是闭标签弹出栈顶。如果不是闭标签就进入开标签处理先找空格把属性剥掉比如a hrefx只保留a。然后检查最后一个字符是不是/比如br/这种自闭合标签在严格的 XML 模型里等价于开和关同时发生所以它不应该入栈只需要给父节点添加一个叶子节点就行。这里有一个我实际写代码时反复出错的地方br/的标签体字符串是br/两个字符都贴在一起如果你直接拿整个字符串去建节点节点名字就变成br/了。所以判断完自闭合之后一定要把末尾的斜杠也剥掉。顺序不能反先剥属性、再剥斜杠、最后建节点。我在代码里专门写了一段注释提醒自己否则下次又来一个img srca/b.png/这种带路径的属性你就等着 Debug 到怀疑人生。3.2 预处理 DFS深度、时间戳、子树大小一次算全我习惯在解析完成之后马上对虚拟根做一次完整的 DFS。这一步把后面查询要用的所有信息一次性算好。每个节点需要记录四个量父节点编号、深度、进入时间 tin、离开时间 tout。深度从虚拟根开始算虚拟根深度记为 0遇到子节点就加 1。tin 和 tout 用一个全局计时器递增进入节点时赋 tin离开节点时赋 tout。这里有一个很多新手会忽略的细节tin 和 tout 的计时器是同一个也就是说每访问一个节点计时器会走两格进入一格、离开一格。你只需要保证每个节点都能拿到这两个值不需要关心它们是不是连续的。判断祖先关系的时候只要求 tin 和 tout 满足严格小于关系中间空几个数完全不影响。还有一个更隐蔽的点如果题目要求找最近的公共祖先或者是否是兄弟节点光是 tin/tout 就不够了。但 UVa 11484 这类题核心仍然落在祖先判断上所以我建议大家先把时间戳这套打扎实。等你哪天做到 LCA 的题会发现这里多算的 depth 和 parent 全都是现成的基础数据代码直接拿来改改就能用。3.3 查询逻辑把题面的关系问答翻译成代码查询部分的输入格式通常是两个标签名。因为同一个标签名可能在文档里出现多次所以第一步要做的不是直接找节点 id而是先收集所有同名的节点。这里有个策略问题如果查询的是A 是否是 B 的祖先而 A 出现多个、B 也出现多个到底判断哪一对我的做法是建立标签名到节点 id 列表的映射然后对每一对候选节点做时间戳判断。如果题目没有特别说明要判断任意一对还是至少存在一对通常会默认每个标签名只对应一个节点或者要求你逐个匹配。稳妥起见我一般会遍历所有同名节点找到第一个满足祖先关系的组合就输出结果。这套逻辑用两重循环实现很简单如果同名节点很多再用别的优化但一般情况下两重循环足够。查询的具体输出格式要看题面有的问 ancestor 返回深度差有的问 parent 返回是不是直接父节点。不管输出什么核心判断就一句用 tin/tout 的包含关系判断祖先再用 depth 差判断是否直接父子。我给出的参考代码里用 lambda 封装了isAncestor这样查询部分的代码读起来非常清晰不会把一堆小于号大于号揉在一起。3.4 完整参考代码C#include bits/stdc.h using namespace std; struct Node { string name; int parent; vectorint children; int depth; int tin, tout; Node(string n , int p -1) : name(n), parent(p), depth(0), tin(0), tout(0) {} }; vectorNode dom; void dfsIterative(int root) { // pair 的第二个数0 表示进入节点1 表示离开节点 stackpairint, int st; st.push({root, 0}); int timer 0; while (!st.empty()) { auto [u, state] st.top(); st.pop(); if (state 0) { dom[u].tin timer; st.push({u, 1}); // 逆序入栈保证子节点按原顺序被访问 for (auto it dom[u].children.rbegin(); it ! dom[u].children.rend(); it) { int v *it; dom[v].depth dom[u].depth 1; st.push({v, 0}); } } else { dom[u].tout timer; } } } bool isAncestor(int a, int b) { return dom[a].tin dom[b].tin dom[b].tout dom[a].tout; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string doc; getline(cin, doc); dom.clear(); dom.emplace_back(#document, -1); stackint openStack; openStack.push(0); size_t pos 0; while (pos doc.size()) { if (doc[pos] ! ) { pos; continue; } size_t end doc.find(, pos); if (end string::npos) break; string tag doc.substr(pos 1, end - pos - 1); pos end 1; if (tag.empty()) continue; // 闭标签弹出栈顶 if (tag[0] /) { if (!openStack.empty()) openStack.pop(); continue; } // 自闭合标签成为叶子节点不入栈 bool selfClose tag.back() /; if (selfClose) tag.pop_back(); // 去掉属性只保留标签名 size_t sp tag.find( ); string name (sp string::npos) ? tag : tag.substr(0, sp); if (name.empty()) continue; int parent openStack.top(); int id dom.size(); dom.emplace_back(name, parent); dom[parent].children.push_back(id); if (!selfClose) openStack.push(id); } dfsIterative(0); // 建立标签名到节点 id 列表的映射 unordered_mapstring, vectorint nameMap; for (int i 0; i (int)dom.size(); i) { nameMap[dom[i].name].push_back(i); } // 查询这里以A 是否为 B 的祖先为例 string qa, qb; while (cin qa qb) { auto itA nameMap.find(qa); auto itB nameMap.find(qb); if (itA nameMap.end() || itB nameMap.end()) { cout not found \n; continue; } bool ok false; for (int a : itA-second) { for (int b : itB-second) { if (isAncestor(a, b)) { cout ancestor depth diff dom[b].depth - dom[a].depth \n; ok true; break; } } if (ok) break; } if (!ok) cout no relation \n; } return 0; }代码里有几个地方值得额外说明。首先是getline读取整行文档这要求输入格式把整个文档放在一行里。如果题目把文档拆成多行你要写成循环不断读入直到遇到空行或者特定结束标记。其次是unordered_map记录同名节点列表这个设计在查询时避免了每次全数组扫描是一个简单有效的优化。最后是迭代 DFS 里用pairint,int模拟递归栈这一招在后面讲爆栈问题的时候还会再提。4. 排坑与细节我实际提交时踩过的那些坑4.1 坑一文本节点和空白字符导致的解析错位真实文档里标签之间不可能干干净净全是标签会有换行符、空格、文本内容比如pHello World/p中间夹着文字。很多第一次写这道题的人会把文字也当节点建进去结果树里多出一堆文本节点查询全部错乱。我的处理原则很简单如果不是以开头的字符一律跳过。因为题目要的是标签组成的结构树文本内容不影响包含关系。你甚至不需要去区分Hello World是不是某个节点的文本子节点直接忽略即可。这个决策来自一个很重要的题感先想清楚题目到底需要什么信息再把不需要的信息果断丢掉解析器会清爽很多。空白字符还有一个隐藏问题如果文档字符串里存在和之间夹着换行的情况find()依然能找到但你要小心标签体里可能混进\r这种字符。UVa 的老评测机跑在 Linux 上但输入文件可能是 Windows 风格行尾会有\r剥属性的时候一定要记得先把标签体里的空白字符统一处理掉否则标签名会变成p\r之类的东西匹配永远对不上。4.2 坑二递归爆栈改用迭代 DFS我第一次提交这题的时候DFS 部分写的是递归。本地测试小数据完全没问题一上 UVa 就 Runtime Error查了半天才发现是爆栈。UVa 的评测环境栈空间给得相当保守递归深度一旦到几万层就直接崩而题面的数据范围完全可能构造出一条 10 万层的链式嵌套。代码里我特意用了迭代 DFS用pairint,int模拟进入/离开两个状态。这是把递归改成迭代的通用套路每次循环从栈里弹出一个状态如果是进入状态就分配 tin、把离开状态压回去、再把所有子节点按进入状态压进去如果是离开状态就分配 tout。整个过程和递归版本做的操作完全一样唯一的区别是不依赖系统调用栈。这个坑值得单独拎出来说因为不是只有这一道题会遇到。凡是树上问题只要数据可能构造链式结构你就应该有意识地避免深递归。C 的递归栈深度大概几千到几万层就会出问题而迭代栈的上限取决于你分配多少内存。我现在的习惯是树的高度的量级不确定时默认写迭代省得被评测机背刺。4.3 坑三标签名大小写与重复标签名的处理DOM 里标签名严格说是不区分大小写的P和p是同一个标签。但 UVa 这类题目的题面未必按 HTML 标准来有的输入里大小写混合有的输入约定全小写。我的建议是不要赌解析的时候统一转成小写查询的时候也转小写两边保持一致就不会踩到大小写匹配失败的坑。重复标签名是另一个容易想当然的点。文档里div会出现几十次查询里只给你div p你如果直接拿一个mapstring,int记录标签名对应唯一节点 id那后面的 div 会把前面的覆盖掉查询结果就完全错了。我在前面代码里设计的unordered_mapstring, vectorint就是为了解决这个问题一个标签名对应一个节点 id 列表查询时遍历列表。当然如果题面额外保证了每个标签名唯一你可以简化映射但写的时候多留一手对不确定的数据总能更从容。4.4 常见问题速查表症状可能原因解决办法解析后节点数量明显偏多把文本内容当成节点建树扫描时跳过所有不以开头的内容查询结果全部是 no relation属性没剥干净节点名带了空格后的内容找标签体里的第一个空格截断取前半部分自闭合标签后栈状态错乱br/被当成普通开标签压栈先判断末尾/自闭合不进栈Runtime Error递归 DFS 深度过大改成pairint,int状态栈的迭代 DFS同名标签匹配错误用唯一 id 记录了重复标签名改用标签名到 id 列表的映射标签名尾部有\r导致匹配失败Windows 行尾符混入解析时统一去空白字符再存名字这张表里的前三个问题是解析阶段最常见的后三个是我自己真实踩过的。你可以发现一个规律几乎每个坑都来自输入数据和题面假设不完全一致。Competitive Programming 里有一句话叫不要相信样例要相信题面但题面也会留白这时候唯一能依靠的就是你对边界条件的警觉。多写几组刁钻的自测数据比盲目提交试错要高效得多。5. 从 UVa 11484 能带走什么一道题的迁移价值5.1 解析器思维栈在工程场景里的真正用途很多人刷完这道题就把代码扔了觉得不过是一个模拟题。但如果你以后写过任何前端工具、模板引擎、配置文件解析器你会发现这题的解析逻辑和真实工程代码殊途同归。HTML 解析器、JSON 解析器、Markdown 解析器核心都是把字符串流变成结构树而处理嵌套结构的通用工具就是栈。我在真实项目里写过一次简单的模板渲染器输入模板里有{{if}}...{{/if}}这种嵌套块当时第一反应就是 UVa 11484 的栈逻辑遇到开始标记就压栈遇到结束标记就弹栈栈顶永远是当前嵌套块的父级。这个模式一旦你真正理解过一次后面遇到任何成对标记问题都能条件反射地想到栈。这就是刷题的价值——不是背题是积累可以迁移的模式。还有属性剥离那段逻辑放到工程里就是 HTML sanitizer 的雏形。真实世界里的a hrefjavascript:alert(1)带各种奇怪的属性你怎么安全地只保留标签名剥属性、去空白、忽略文本节点这些动作在 UVa 11484 里练熟了以后处理用户输入时你会下意识想到先清洗再解析而不是直接信任原始字符串。5.2 树上时间戳不只是这道题更是树论题的基础功DFS 时间戳的迁移价值比解析器更大。我后来做过很多树上问题比如树状数组维护子树和、判断路径上的点、离线处理子树查询全都默认使用 tin/tout 这套时间戳。它的本质是把树压成一维序列让树上的区间查询变成数组上的区间查询这一个思想撑起了树上数据结构的一大半题目。给你一个具体的例子假设题目变成每次查询某个节点子树里所有 a 标签的个数你把 DFS 时间戳一算每个节点对应一个区间[tin, tout]子树查询就变成了统计落在某个连续区间内的特定标签节点数可以用离线排序加树状数组解决。这个推导过程里时间戳就是整道题的钥匙。没有它你要么暴力遍历子树要么写复杂的高级数据结构有了它问题难度直接降一档。所以我的建议是做 UVa 11484 的时候不要只满足于 AC。花半小时想一想如果查询变成别的形式你的时间戳和 depth 数据还能干什么把这个问题想透你从这道题里拿走的东西就远超一道题的分数了。我自己刷题时的习惯是每道题留三样东西核心数据结构的模板、边界条件的清单、可迁移的思考模式。UVa 11484 的三样都很有价值——栈解析是模板自闭合和重复标签名是边界清单时间戳是通用思考模式。如果你也想把这题吃透可以试着再写一个版本把查询改成输出 A 到 B 的路径或者判断 A 和 B 是否是兄弟节点你会发现原本的框架稍微扩展一下就能胜任。这就是一道好题该有的样子它不考偏题怪题考的是你愿不愿意把一个通用方法用到极致。
阅读完成 · 觉得有帮助？
