企业官网建设流程全解析

打开 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>没有对应的</br>，<p>甚至可以自动闭合。但 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 href="x">只保留a。然后检查最后一个字符是不是/，比如<br/>，这种自闭合标签在严格的 XML 模型里等价于"开和关同时发生"，所以它不应该入栈，只需要给父节点添加一个叶子节点就行。

这里有一个我实际写代码时反复出错的地方：<br/>的标签体字符串是br/，两个字符都贴在一起，如果你直接拿整个字符串去建节点，节点名字就变成br/了。所以判断完自闭合之后，一定要把末尾的斜杠也剥掉。顺序不能反：先剥属性、再剥斜杠、最后建节点。我在代码里专门写了一段注释提醒自己，否则下次又来一个<img src="a/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; vector<int> children; int depth; int tin, tout; Node(string n = "", int p = -1) : name(n), parent(p), depth(0), tin(0), tout(0) {} }; vector<Node> dom; void dfsIterative(int root) { // pair 的第二个数：0 表示进入节点，1 表示离开节点 stack<pair<int, 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); stack<int> 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_map<string, vector<int>> 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 里用pair<int,int>模拟递归栈，这一招在后面讲爆栈问题的时候还会再提。

4. 排坑与细节：我实际提交时踩过的那些坑

4.1 坑一：文本节点和空白字符导致的解析错位

真实文档里标签之间不可能干干净净全是标签，会有换行符、空格、文本内容，比如<p>Hello World</p>中间夹着文字。很多第一次写这道题的人会把文字也当节点建进去，结果树里多出一堆文本节点，查询全部错乱。

我的处理原则很简单：如果不是以<开头的字符，一律跳过。因为题目要的是标签组成的结构树，文本内容不影响包含关系。你甚至不需要去区分"Hello World"是不是某个节点的文本子节点，直接忽略即可。这个决策来自一个很重要的题感：先想清楚题目到底需要什么信息，再把不需要的信息果断丢掉，解析器会清爽很多。

空白字符还有一个隐藏问题：如果文档字符串里存在<和>之间夹着换行的情况，find('>')依然能找到，但你要小心标签体里可能混进\r这种字符。UVa 的老评测机跑在 Linux 上，但输入文件可能是 Windows 风格，行尾会有\r，剥属性的时候一定要记得先把标签体里的空白字符统一处理掉，否则标签名会变成p\r之类的东西，匹配永远对不上。

4.2 坑二：递归爆栈，改用迭代 DFS

我第一次提交这题的时候，DFS 部分写的是递归。本地测试小数据完全没问题，一上 UVa 就 Runtime Error，查了半天才发现是爆栈。UVa 的评测环境栈空间给得相当保守，递归深度一旦到几万层就直接崩，而题面的数据范围完全可能构造出一条 10 万层的链式嵌套。

代码里我特意用了迭代 DFS，用pair<int,int>模拟"进入/离开"两个状态。这是把递归改成迭代的通用套路：每次循环从栈里弹出一个状态，如果是进入状态就分配 tin、把离开状态压回去、再把所有子节点按进入状态压进去；如果是离开状态就分配 tout。整个过程和递归版本做的操作完全一样，唯一的区别是不依赖系统调用栈。

这个坑值得单独拎出来说，因为不是只有这一道题会遇到。凡是树上问题，只要数据可能构造链式结构，你就应该有意识地避免深递归。C++ 的递归栈深度大概几千到几万层就会出问题，而迭代栈的上限取决于你分配多少内存。我现在的习惯是：树的高度的量级不确定时，默认写迭代，省得被评测机背刺。

4.3 坑三：标签名大小写与重复标签名的处理

DOM 里标签名严格说是不区分大小写的，<P>和<p>是同一个标签。但 UVa 这类题目的题面未必按 HTML 标准来，有的输入里大小写混合，有的输入约定全小写。我的建议是不要赌，解析的时候统一转成小写，查询的时候也转小写，两边保持一致，就不会踩到大小写匹配失败的坑。

重复标签名是另一个容易想当然的点。文档里<div>会出现几十次，查询里只给你div p，你如果直接拿一个map<string,int>记录"标签名对应唯一节点 id"，那后面的 div 会把前面的覆盖掉，查询结果就完全错了。我在前面代码里设计的unordered_map<string, vector<int>>就是为了解决这个问题：一个标签名对应一个节点 id 列表，查询时遍历列表。当然，如果题面额外保证了每个标签名唯一，你可以简化映射，但写的时候多留一手，对不确定的数据总能更从容。

4.4 常见问题速查表

这张表里的前三个问题是解析阶段最常见的，后三个是我自己真实踩过的。你可以发现一个规律：几乎每个坑都来自"输入数据和题面假设不完全一致"。Competitive Programming 里有一句话叫"不要相信样例，要相信题面"，但题面也会留白，这时候唯一能依靠的就是你对边界条件的警觉。多写几组刁钻的自测数据，比盲目提交试错要高效得多。

5. 从 UVa 11484 能带走什么：一道题的迁移价值

5.1 解析器思维：栈在工程场景里的真正用途

很多人刷完这道题就把代码扔了，觉得不过是一个模拟题。但如果你以后写过任何前端工具、模板引擎、配置文件解析器，你会发现这题的解析逻辑和真实工程代码殊途同归。HTML 解析器、JSON 解析器、Markdown 解析器，核心都是"把字符串流变成结构树"，而处理嵌套结构的通用工具就是栈。

我在真实项目里写过一次简单的模板渲染器，输入模板里有{{if}}...{{/if}}这种嵌套块，当时第一反应就是 UVa 11484 的栈逻辑：遇到开始标记就压栈，遇到结束标记就弹栈，栈顶永远是当前嵌套块的父级。这个模式一旦你真正理解过一次，后面遇到任何"成对标记"问题都能条件反射地想到栈。这就是刷题的价值——不是背题，是积累可以迁移的模式。

还有属性剥离那段逻辑，放到工程里就是 HTML sanitizer 的雏形。真实世界里的<a href="javascript:alert(1)">带各种奇怪的属性，你怎么安全地只保留标签名？剥属性、去空白、忽略文本节点，这些动作在 UVa 11484 里练熟了，以后处理用户输入时你会下意识想到"先清洗再解析"，而不是直接信任原始字符串。

5.2 树上时间戳：不只是这道题，更是树论题的基础功

DFS 时间戳的迁移价值比解析器更大。我后来做过很多树上问题，比如树状数组维护子树和、判断路径上的点、离线处理子树查询，全都默认使用 tin/tout 这套时间戳。它的本质是"把树压成一维序列"，让树上的区间查询变成数组上的区间查询，这一个思想撑起了树上数据结构的一大半题目。

给你一个具体的例子：假设题目变成"每次查询某个节点子树里所有 a 标签的个数"，你把 DFS 时间戳一算，每个节点对应一个区间[tin, tout]，子树查询就变成了"统计落在某个连续区间内的特定标签节点数"，可以用离线排序加树状数组解决。这个推导过程里，时间戳就是整道题的钥匙。没有它，你要么暴力遍历子树，要么写复杂的高级数据结构，有了它，问题难度直接降一档。

所以我的建议是：做 UVa 11484 的时候，不要只满足于 AC。花半小时想一想，如果查询变成别的形式，你的时间戳和 depth 数据还能干什么？把这个问题想透，你从这道题里拿走的东西就远超一道题的分数了。

我自己刷题时的习惯是每道题留三样东西：核心数据结构的模板、边界条件的清单、可迁移的思考模式。UVa 11484 的三样都很有价值——栈解析是模板，自闭合和重复标签名是边界清单，时间戳是通用思考模式。如果你也想把这题吃透，可以试着再写一个版本，把查询改成"输出 A 到 B 的路径"，或者"判断 A 和 B 是否是兄弟节点"，你会发现原本的框架稍微扩展一下就能胜任。这就是一道好题该有的样子：它不考偏题怪题，考的是你愿不愿意把一个通用方法用到极致。