题目翻译

文档对象模型（$\text{Document Object Model}$， $\text{DOM}$）是一种用于表示 $\text{HTML}$ 页面结构的模型。整个文档由嵌套的元素构成。这些元素之间存在一个根元素（父元素），所有其他元素都是它的子元素或后代元素。为了在这些元素间进行遍历，浏览器提供了一系列函数。本题要求在一个给定的简化版 $\text{HTML}$ 文档上，模拟这些函数的一个子集。

为简化问题，我们对 $\text{HTML}$ 文档做出如下定义：

文档的每一行将属于以下两种格式之一：
$1$. <n value='<word>' ，其中 <word> 由一个或多个英文字母组成。
$2$. </n>

格式 $1$ 表示一个新元素的开始（即开始标签），格式 $2$ 表示一个元素的结束（即结束标签）。注意，一个元素内部可以嵌套零个或多个元素，因此 </n> 总是关闭最近打开且尚未关闭的元素。

模拟过程如下：初始时，一个指针指向根元素。每条指令会根据其类型将指针移动到另一个元素。如果指令试图将指针移动到一个不存在的元素（例如，当前元素没有子元素时执行 first_child 指令），则指针保持在当前元素上，不做移动。

---

输入格式

每个测试用例以一行开始，包含一个正整数 $N\le 1000$ 。接下来 $N$ 行，每行给出文档的一行定义。可以假设文档的定义是正确且完整的。然后是一行，包含一个正整数 $I\le 100$ ，表示该测试用例的指令数量。接下来的 $I$ 行，每行包含一条有效指令。最后一个测试用例之后是一个 $N=0$ 的行，表示输入结束。输入文件的每行最多包含 $100$ 个字符。

指令集包括以下四种：

• first_child ：移动到当前元素的第一个子元素。
• next_sibling ：移动到当前元素的下一个兄弟元素。
• previous_sibling ：移动到当前元素的上一个兄弟元素。
• parent ：移动到当前元素的父元素。

---

输出格式

对于每个测试用例，首先输出一行 Case <x>: ，其中 <x> 是测试用例编号（从 $1$ 开始）。然后对于每条指令，输出一行，内容为该指令执行后指针所指向的元素的 value 属性的值。

---

样例输入与输出

样例输入

4
<n value='parent'>
<n value='child'>
</n>
</n>
2
next_sibling
first_child
0

样例输出

Case 1:
parent
child

---

题目分析

本题的核心是模拟 $\text{DOM}$ 树的构建与遍历。我们需要解决两个主要问题：

1. 如何根据输入构建一棵树？ 输入是按照类似 HTML 标签的开闭顺序给出的，这天然地对应了树的深度优先遍历（$\text{DFS}$） 顺序。我们可以使用一个栈来追踪当前正在处理的节点层级。
2. 如何高效地执行遍历指令？ 指令要求我们在树中上下左右（父、子、兄弟）移动。这要求我们的树节点结构不仅要存储数据（ value ），还要存储其与其他节点的关系（父节点指针和子节点列表）。

---

解题思路

步骤一：数据结构设计

我们定义一个 Node 结构体来表示树中的每个节点：

• string value ：存储该节点的值（即 value='...' 中的内容）。
• Node* parent ：指向该节点的父节点的指针。
• vector<Node*> children ：存储指向该节点所有子节点的指针的向量（动态数组）。子节点在这个向量中的顺序就是它们在文档中出现的顺序，这完美地定义了“第一个子节点”和“下一个/上一个兄弟节点”。

步骤二：建树过程（解析输入）

我们使用一个栈 nodeStack 来辅助建树：

1. 遍历输入的每一行 line 。
2. 如果 line 以 <n value=' 开头，说明遇到了一个开始标签：
   • 从字符串中解析出 value 值。
   • 创建一个新的 Node 对象 newNode ，其 value 为解析出的值。
   • 如果栈为空，说明这是根节点。将 root 和当前指针 current 都指向它。
   • 如果栈非空，说明新节点是栈顶节点（即当前打开的元素）的子节点。设置 newNode 的父指针指向栈顶节点，并将 newNode 压入栈顶节点的 children 列表中。
   • 最后，将 newNode 压入 nodeStack 。
3. 如果 line 是 </n> ，说明当前元素结束。将栈顶元素弹出（ nodeStack.pop() ）。
4. 处理完所有行后，完整的 $\text{DOM}$ 树就构建好了。

步骤三：指令模拟过程

指令模拟基于当前指针 current 进行：

• first_child ：检查 current->children 是否为空。若非空，则将 current 更新为 current->children 的第一个元素（索引 $0$ ）。
• next_sibling ：
  • 首先检查 current 是否有父节点（ current->parent != nullptr ）。
  • 如果有，在父节点的 children 列表中，使用 find 函数找到 current 的位置 it 。
  • 如果 it 不是列表的最后一个元素（即 it + 1 != children.end() ），则将 current 更新为 *(it + 1) 。
• previous_sibling ：逻辑与 next_sibling 类似，但检查 it 是否为列表的第一个元素，并移动到 *(it - 1) 。
• parent ：检查 current->parent 是否存在，若存在则更新 current 为 current->parent 。
• 每次执行指令后，输出 current->value 。

关键点：所有移动指令在执行前，都必须检查目标节点是否存在。如果移动条件不满足（如没有子节点、没有兄弟节点、没有父节点），则指针 current 保持不变。这与题目描述完全一致。

步骤四：内存管理

虽然题目规模较小（ $N\le 1000$ ），动态分配的节点内存不会造成问题，但在一个完善的程序中，应在所有测试用例处理完毕后释放所有节点内存，以避免潜在的内存泄漏。本题的参考代码为了简洁省略了这一步，在实际应用中应予以考虑。

---

复杂度分析

• 时间复杂度：
  • 建树：需要遍历 $N$ 行输入，每行处理为 $O(1)$ （字符串查找和节点创建），故建树为 $O(N)$ 。
  • 指令模拟：每条指令在树中移动，最坏情况下需要遍历兄弟列表（ find 操作），复杂度为 $O(C)$ ，其中 $C$ 是当前节点的兄弟数量。总共 $I$ 条指令，最坏总复杂度为 $O(I\ast N)$ 。考虑到 $N\le 1000$ 且 $I\le 100$ ，这是完全可以接受的。
• 空间复杂度：主要用来存储整棵树，节点数为 $O(N)$ ，每个节点存储值、指针和子节点向量，总空间复杂度为 $O(N)$ 。

---

代码实现

// Document Object Model
// UVa ID: 11484
// Verdict: Accepted
// Submission Date: 2026-01-24
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

// 定义DOM树节点结构体
struct Node {
    string value; // 节点的值
    Node* parent; // 指向父节点的指针
    vector<Node*> children; // 存储所有子节点指针的向量
    Node(const string& v) : value(v), parent(nullptr) {} // 构造函数
};

int main() {
    int caseNum = 1; // 用例编号
    int n;
    // 循环处理每个测试用例，直到遇到 n=0
    while (cin >> n && n) {
        cin.ignore(); // 忽略n后面的换行符
        vector<string> lines(n);
        for (int i = 0; i < n; ++i) getline(cin, lines[i]); // 读入文档的每一行

        Node* root = nullptr; // 树的根节点
        Node* current = nullptr; // 当前指针，初始为nullptr
        stack<Node*> nodeStack; // 辅助建树的栈

        // 步骤一：构建DOM树
        for (const string& line : lines) {
            // 判断是否为开始标签
            if (line.find("<n value='") != string::npos) {
                // 解析value属性的值
                int start = line.find("'") + 1;
                int end = line.find_last_of("'");
                string value = line.substr(start, end - start);
                // 创建新节点
                Node* newNode = new Node(value);
                if (nodeStack.empty()) {
                    // 栈为空，新节点是根节点
                    root = newNode;
                    current = newNode; // 初始指针指向根节点
                } else {
                    // 栈非空，新节点是栈顶节点的子节点
                    newNode->parent = nodeStack.top();
                    nodeStack.top()->children.push_back(newNode);
                }
                nodeStack.push(newNode); // 新节点入栈
            } else if (line == "</n>") {
                // 遇到结束标签，关闭当前栈顶元素
                nodeStack.pop();
            }
        }

        int i;
        cin >> i; // 读入指令数量
        vector<string> instructions(i);
        for (int j = 0; j < i; ++j) cin >> instructions[j]; // 读入所有指令

        // 输出用例编号
        cout << "Case " << caseNum++ << ":" << endl;
        // 重置当前指针为根节点，开始模拟指令
        current = root;
        for (const string& instr : instructions) {
            if (instr == "first_child") {
                // 移动到第一个子节点
                if (!current->children.empty()) current = current->children[0];
            } else if (instr == "next_sibling") {
                // 移动到下一个兄弟节点
                if (current->parent) {
                    vector<Node*>& siblings = current->parent->children;
                    auto it = find(siblings.begin(), siblings.end(), current);
                    if (it + 1 != siblings.end()) current = *(it + 1);
                }
            } else if (instr == "previous_sibling") {
                // 移动到上一个兄弟节点
                if (current->parent) {
                    vector<Node*>& siblings = current->parent->children;
                    auto it = find(siblings.begin(), siblings.end(), current);
                    if (it != siblings.begin()) current = *(it - 1);
                }
            } else if (instr == "parent") {
                // 移动到父节点
                if (current->parent) current = current->parent;
            }
            // 输出执行指令后当前节点的值
            cout << current->value << endl;
        }
    }
    return 0;
}

代码要点说明：

1. 建树：使用栈完美匹配了标签的嵌套关系。
2. 指令模拟：通过节点结构体中存储的 parent 和 children 关系，高效地实现了四种移动操作。
3. 边界处理：所有指令在执行移动前都进行了合法性检查（指针非空、容器非空、迭代器有效等），确保了程序的健壮性。
4. 输出格式：严格按照题目要求，先输出用例标题，再为每条指令输出一行结果。

此解法思路清晰，实现直接，能够有效解决题目提出的 $\text{DOM}$ 树模拟问题。