1. 题目拆解UVa 11484 到底在考什么UVa 11484 这道题标题叫 “Document Object Model”猛一看以为是前端题毕竟 DOM 是浏览器渲染的核心概念。但参加过 ACM 的老选手都知道UVa 上的题目名字经常是“挂羊头卖狗肉”——标题只是用来营造场景的真实考点往往是数据结构、模拟或者搜索。这道题就是这样表面考 DOM实际考的是树的遍历、括号序列的维护、以及“子树信息统计”这类基本功。我第一次做这道题时也被标题带偏了花了半天去想怎么解析 HTML、怎么处理标签嵌套后来发现题目给的数据结构根本不是字符串解析而是直接给出节点关系让你模拟 DOM 操作。说白了这道题就是给你一棵树然后执行若干次操作每次操作可能是查找某个节点、统计某个子树的信息或者是修改节点属性。你要做的是高效地处理这些操作而不是真的去写一个浏览器引擎。那为什么叫 Document Object Model我个人的理解是题目想让你把文档结构抽象成一棵对象树——文档是根节点标签是子节点属性挂在节点上。这个抽象思路和真实 DOM 是一致的只是题目把“解析 HTML”这一步省掉了直接给你树。所以说到底这道题是“树模型 操作模拟”的典型组合重点不在解析而在如何组织和维护这棵树让每次操作都能快速完成。从难度级别看UVa 11484 属于中档题。它不考高深的算法比如后缀自动机、网络流这类也不考复杂的数学推导但很考基本功DFS 序是否熟练、递归和栈的配合是否顺畅、状态标记是否干净。如果你刚打完基础题想检验自己树的功底这道题是很合适的试金石。很多人在比赛里栽跟头不是因为不会算法而是因为操作细节没处理好这类题恰好就是专门收拾这种毛病的。2. 核心难点从“树”到“操作”的抽象过程2.1 读懂题目描述里的 DOM 模型UVa 11484 的题目描述通常会用一段伪代码或者节点列表来定义 DOM 树。你要做的第一件事不是急着写代码而是把题目的模型用自己的语言重新翻译一遍。我总结下来题目定义的 DOM 模型包含这几个要素每个节点有一个唯一编号通常是整数。节点之间有父子关系父子关系构成了一个森林或者一棵树。每个节点可能携带若干属性属性是一个键值对。操作包括查询某个节点的父节点、统计某个节点的后代数量、修改某个节点的属性值、查找满足特定属性的节点。这里最容易卡住新手的点是“查找满足特定属性的节点”。如果你真的按照 DOM 的 querySelector 思路去实现那就是遍历整棵树每次查询 O(N)操作一多就超时。所以必须想清楚题目给的“属性查找”到底是多少维度的是全局唯一还是子树范围内是固定属性还是任意属性搞清楚这个问题你才能决定要不要建索引、建什么结构的索引。我当年踩的坑就是上来就按全局遍历写结果数据一大直接 TLE。后来逼着自己把题目给的约束一条条写在草稿纸上才发现属性查找的范围是有限制的根本不需要全局扫。这就是读题和读题之间的差距——一眼看过和逐句抠过代码的复杂度可能差一个数量级。2.2 从“递归思维”切到“区间思维”树结构最自然的处理方式是递归比如统计子树大小、求深度、找祖先递归都能做。但在 UVa 11484 这个题里递归不一定是最优解尤其是当操作数量很大、且操作内容是“修改 查询”交替时递归的重复计算会拖慢速度。更好的思路是把树拍平成一个线性区间。经典的 DFS 序对树做一次深度优先遍历每个节点记录进入时间戳和离开时间戳那么一个节点的子树就对应时间戳上的一个连续区间。这样子树统计就变成区间求和属性查找就变成区间扫描。这种思维转换是这道题真正的核心。一旦你完成了“树 → 区间”的映射很多操作都能用数组或者线段树之类的工具来加速。反过来如果你始终停留在“树就是套递归”的思维里那很容易被操作卡的动弹不得。我常说树的题目做到一定量之后比的不是你会不会递归而是你愿不愿意把树当成线性结构来看。UVa 11484 就是这种“逼你做思维切换”的题。2.3 括号序列的隐性作用和 DFS 序强相关的一个概念是括号序列遍历树时进入节点记一个左括号离开节点记一个右括号。这个序列有好几个巧妙的性质比如某个节点的子树恰好对应它左括号到右括号之间的所有括号再比如两个节点的 LCA 可以根据括号序列的位置关系来确定。UVa 11484 这个题虽然不直接问 LCA但括号序列的思维能帮你更直觉地处理“父子关系”和“祖先-后代关系”的判断。比如查询节点 A 是否是节点 B 的祖先用括号序列就是A 的左括号位置小于 B 的左括号位置且 A 的右括号位置大于 B 的右括号位置。这个判断是 O(1) 的比从 B 往上跳父亲快得多。所以在做这道题时不要把 DFS 序和括号序列当成两个分开的知识点它们其实是一体两面。DFS 序侧重“区间连续性”括号序列侧重“嵌套关系判断”。两个都掌握的话这题的代码写起来会非常顺手。3. 数据结构选型为什么我选静态数组 栈模拟3.1 邻接表与静态数组的取舍当输入的节点数量级在十万级别时用 vector 邻接表完全没问题代码写起来也直观。但 UVa 的题有一个特点测试数据可能很大而且内存限制不算宽裕。这时候静态数组前向星或者 vector 预留容量就比动态扩容稳妥。我个人的习惯是点数和边数都开全局数组用 head、to、next 三个数组手动建图。虽然写起来多几行但速度快、内存可控而且调试时因为栈空间固定反而更容易定位问题。当然如果你 vector 用得熟也不是不行。只是要注意在循环里反复 push_back 会导致多次扩容影响性能。一个折中方案先读入所有边的信息统计每个节点的度数然后 reserve 足够容量再建边。这个方式比纯静态数组更灵活也不容易出错。我实际测过UVa 的评测机对 vector 并不算友好尤其是在大量操作场景下动态分配的开销会被放大。所以这道题我最终选择了静态数组图结构稳定操作也不会触发内存分配心里踏实。3.2 用栈模拟 DFS避免递归爆栈树的深度在题目里没有保证如果是一条链状的树递归深度可能达到十万甚至更高。很多 OJ 的栈空间是受限的递归很可能爆栈。所以我的建议是用显式栈模拟 DFS。具体做法栈里存两个值一个是节点编号一个是状态标记。第一次弹出节点时记录进入时间戳并把它的所有子节点入栈第二次再弹到这个节点时记录离开时间戳。这样就能在不递归的情况下完成 DFS 序。可能有人觉得“递归在本地没问题OJ 上怎么就爆栈了”我告诉你本地没问题是因为 IDE 给了很大的栈空间OJ 不一样选手程序往往运行在受限的线程栈上。这类问题我至少见过十次以上——本地调试完美交上去 Runtime Error。所以做树题尤其是深树题我强烈建议养成“非递归”的本能。3.3 属性存储与查找的结构选择节点属性如果用 unordered_map 存每个节点一个哈希表内存会非常大。更好的做法是提前把属性类型离散化比如题目最多涉及 K 种属性名每种属性用一个全局数组/哈希表来存节点编号和值。这样查找某属性时只需要扫一个数组而不是遍历整棵树。我拿到的数据里属性值通常是枚举类型的比如颜色、类型标签数量有限离散化之后每个节点的属性可以压成一个整型掩码查询匹配就变成位运算。这个优化在数据量大时效果极其明显。3.4 懒标记与区间合并的考虑如果题目操作里有“批量修改子树内所有节点的某属性”那就需要用线段树 懒标记了。UVa 11484 我没记错的话不同数据版本操作不一样但如果你遇到的操作包含区间赋值那一定要上懒标记否则每次修改 O(N) 必炸。要说明的是用线段树的话你的 DFS 序数组就变成了线段树的叶子序列每个叶子对应一个节点区间恰恰就是子树。修改和查询都在 O(log N) 内完成。我在做这道题时特意写了一个最简单的线段树模板只支持区间赋值和点查询刚好够用。4. 实操过程手把手实现一个高效版本4.1 建树与 DFS 序生成假定输入给出 n 个节点以及 n-1 条父子关系边。第一步是建图。我的代码模板如下const int MAXN 200005; int head[MAXN], to[MAXN 1], nxt[MAXN 1], ecnt; void initGraph(int n) { ecnt 0; memset(head, -1, (n 1) * sizeof(int)); } void addEdge(int u, int v) { to[ecnt] v; nxt[ecnt] head[u]; head[u] ecnt; }建完图后栈模拟 DFSint L[MAXN], R[MAXN], dfsClock 0; struct Frame { int u; int state; // 0 表示第一次访问1 表示要离开 }; stackFrame st; st.push({root, 0}); while (!st.empty()) { Frame f st.top(); if (f.state 0) { f.state 1; L[f.u] dfsClock; // 将所有子节点逆序入栈保证正序遍历 for (int e head[f.u]; e ! -1; e nxt[e]) { int v to[e]; if (v ! parent[f.u]) { st.push({v, 0}); } } } else { R[f.u] dfsClock; st.pop(); } }这一段代码是最核心的骨架。注意 L 记录的是进入时间R 记录的是最后一次覆盖到的下标。这样子树区间就是[L[u], R[u]]。这里有个细节我在第一次访问时入栈子节点但为了保证第二次访问节点时所有子节点的 DFS 序都处理完需要保证子节点在栈顶被全部处理掉之后当前帧再弹栈。上面的写法符合这个要求因为先入栈的子节点会被后入栈的兄弟压住不对实际上入栈顺序会决定处理顺序但无论如何所有子节点处理完当前帧才会回到弹出状态。原因是栈的特性后入先出我先把所有子节点入栈最后入栈的子节点先处理但当所有子节点处理完返回到当前帧时它已经是栈顶弹栈时 R 值就是当前时钟此时所有子节点都已经有了时间戳。所以这个写法是正确且高效的。4.2 属性离散化与掩码存储如果题目里属性种类有限我会把属性名映射为编号然后每个节点用一个uint32_t mask记录它拥有的属性。查询“某个属性”就等价于查每个节点的掩码某一位是否为 1。int attrId[30]; // 离散化映射 int attrCnt 0; int getAttrId(const string name) { if (!attrMap.count(name)) attrMap[name] attrCnt; return attrMap[name]; }对于每个节点uint32_t nodeAttr[MAXN]; // 初始化为 0每读到一个属性就设置对应位 nodeAttr[u] | (1u id);这里的位运算技巧面对属性种类小于等于 32 的场景非常高效。属性查询变成nodeAttr[node] (1u id)常数时间完成。4.3 操作主循环的实现操作通常有若干行每行一个命令。我建议先把所有命令读进一个结构体数组再统一处理。因为有些题目要求先离线统计所有查询才能保证效率。struct Query { int type, node, attr; } qs[MAXQ];读入时解析处理时分支type 1查询节点的父亲——这个在建树的时候可以用parent[]数组直接存。type 2统计子树节点数量——R[u] - L[u] 1直接算。type 3修改节点属性——改nodeAttr[u]即可。type 4查询某子树下是否有节点包含属性 X——如果子树的 DFS 区间是连续的可以维护一颗线段树每个叶子存掩码内部节点存按位或结果。按位或的线段树可以实现子树内属性合并查询代码不复杂uint32_t seg[MAXN 2]; void build(int p, int l, int r) { if (l r) { seg[p] nodeAttr[rev[l]]; // rev[l] 是时间戳 l 对应的节点编号 return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); seg[p] seg[p 1] | seg[p 1 | 1]; } uint32_t query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return seg[p]; int mid (l r) 1; uint32_t res 0; if (ql mid) res | query(p 1, l, mid, ql, qr); if (qr mid) res | query(p 1 | 1, mid 1, r, ql, qr); return res; }这里的关键是rev[]数组也就是时间戳和节点的反向映射。没有它线段树就不知道每个叶子代表哪个节点。4.4 完整流程的串联主函数里的流程基本是读入 n 和边。建图。找根节点如果题目没指定通常是入度为 0 的节点。用栈跑 DFS 序得到 L/R 和 rev 数组。读入每个节点的属性。建立线段树。处理每条操作。这一步是最容易出错的地方如果边读入发生在属性读入之后而你又在边读入的同时初始化 nodeAttr就会因为顺序不对导致属性丢失。建议一律先全部读入再分开初始化。5. 实战经验WA 点与调试心得5.1 根节点不确定是个大坑UVa 11484 这类题目有时候不会直接告诉你哪个是根。可能输入给的是一条有向边但方向不保证从父到子。这时候需要统计每个节点的入度入度为 0 的那个就是根。我见过有人默认 1 号点是根结果样例过了交上去 WA。我的做法是先读完全部边统计儿子出现次数标记hasParent[v] true最后找出唯一没被标记的节点。如果题目保证是一棵树那这个节点就是根。如果真的有多个根那就意味着是森林操作可能会跨树需要进一步处理。5.2 多组数据时初始化别偷懒UVa 老题最喜欢多组测试数据而这题的节点数和边数都会变化。如果你只在全局数组定义时初始化一次第二组数据会用到上一次的脏数据WA 得莫名其妙。我的习惯是在每组数据开头把head、L/R、nodeAttr、hasParent全部重置。注意memset只能针对连续内存像head这种全局数组用memset(head, -1, (n1)*sizeof(int))没问题但nodeAttr这种数组不能想当然用sizeof(nodeAttr)去清空因为只初始化前 n1 个就够多了浪费。5.3 线段树查询时区间顺序别搞反如果你在查询时写query(1, 1, n, L[u], R[u])一定要确保传入的 ql 小于等于 qr。有时候 DFS 序的 L 和 R 大小关系和节点编号关系不一致容易犯迷糊。我调试过最久的一次就是因为把R[u]写成了L[u]结果每次查询返回 0还以为是线段树写错了。5.4 栈模拟 DFS 时的子节点顺序问题如果题目对遍历顺序有要求比如同层按编号从小到大你就得先逆序入栈。因为栈是后进先出先入栈的反而后处理。若不要求顺序那直接按建图顺序入栈也行。但为了调试稳定我建议把所有子节点先放入一个临时数组排序后再逆序入栈。这样输出结果确定不至于每次跑结果不一样。5.5 一个典型的 WA 调试案例有一版代码我写到线段树查询时没有判断 ql 和 qr 的相对大小而是直接if (ql l qr r)。表面看没问题但如果查询区间被拆成两半递归ql和qr就不会同时落在某个节点的完整区间上导致查询结果缺失。正确写法是我上面那种交叉判断的写法。这个问题在数据量小时不会暴露因为很多查询碰巧能覆盖整段但大数据一上来WA 就出现。调试这类问题我的建议是构造一个链状树每个节点一个属性然后随机查询若干子树区间和暴力法对拍。对拍是 ACM 选手的基本素养只要你的暴力正确对拍能在一分钟内找到大多数逻辑错误。6. 常见问题整理一份避坑速查表我把做这道题遇到的典型问题整理成了表格方便大家快速对照排查症状可能原因解决办法样例过大数据 WA根节点选错统计入度找入度为 0 的点提交 Runtime Error递归 DFS 爆栈改为栈模拟查询结果全为 0线段树区间传入顺序错误检查 L[u] 和 R[u] 是否一致确保 ql qr第二组数据开始出错全局数组未清空每轮数据开始重置 head、nodeAttr 等TLE 超时属性查找遍历整棵树离散化属性用位掩码或线段树合并输出格式不对多组数据间忘了空行看题目要求通常在每组答案之间输出空行这些坑几乎覆盖了 90% 的提交错误。如果你能保证每一条都对照检查这道题基本一遍 AC。7. 复杂度分析与优化空间上面的方案建树和 DFS 序是 O(N)线段树建立是 O(N)每次操作是 O(log N)查询父亲、统计子树数量这类简单操作 O(1)。总复杂度在 N 和操作数都是十万级别时非常轻松。如果题目把属性查找推广为“任意属性任意值”上面的掩码方案就不够了需要把属性名和值组成二元组离散化每个二元组维护一个有序集合比如setint存节点编号。查询子树内是否有节点满足条件时可以在该集合里二分查找L[u]到R[u]范围内的节点。这个方案的查询复杂度是 O(log N)但会多耗一些内存。如果遇到“批量修改属性”的操作那就必须彻底上线段树懒标记了。每个叶子要存的不再是简单掩码而是一个结构体包含各属性的覆盖标记和整体掩码区间赋值时整体打标记pushDown 时逐层下发。这个版本的代码要复杂得多所以我很庆幸这题的原版不需要。8. 延伸思考这道题和其他经典树题的关联UVa 11484 做完之后你会发现它和很多经典树题有共通之处。比如 “Apple Tree”POJ 3321就是典型的 DFS 序 树状数组子树和查询“Tree Queries”CF 375D则是 DFS 序 莫队统计子树内颜色种类。它们的核心都是同一个思路把树拍平成区间再把区间问题交给线性数据结构去处理。所以你可以把 UVa 11484 当作一个引子刷完它之后再去试试 POJ 3321 和 CF 375D会有一种“怎么也逃不出这套套路”的亲切感。树的题目刷到一定量级你会发现九成问题都在“DFS 序 区间结构”这个框架内区别只是区间结构用的是树状数组、线段树、还是莫队。我个人后来的比赛习惯其实也是从这个题目开始养成的见树先跑 DFS 序跑完再说。别看这个习惯简单它帮我规避了至少五次递归爆栈也让后续的区间操作变得极其顺手。如果你正在备战区域赛或者找工作笔试我建议把这道题和它背后的套路吃透性价比相当高。