HDU 4041 Eliminate Witches！：樹的先序遍歷模擬與棧隊列應用

題目背景

魔法少女圓香在樹狀迷宮中消滅女巫。迷宮以樹表示，節點為房間，邊為通道。圓香從根節點開始，遵循規則：

1. 進入根節點。
2. 若當前房間有女巫，立即消滅。
3. 若有子節點含女巫，選擇最左側子節點進入。
4. 直到某節點所有子樹的女巫被消滅，才回溯到父節點。

輸入為一個括號字串表示樹結構（如 walpurgis(charlotte(patricia,gertrud),elly,gisela)），要求輸出：節點數、消滅順序的女巫名字、圓香移動軌跡（節點編號對）。

解題思路：模擬先序遍歷

此過程本質是樹的先序遍歷（根→左→右），但需記錄「進入」與「退出」每個節點的時刻，形成軌跡。

關鍵觀察

• 女巫名字由小寫字母組成，以 (、)、, 分隔。
• 遍歷順序即為名字在字串中首次出現的順序（先序）。
• 移動軌跡：每次下行到子節點輸出 父 子，每次回溯到父節點輸出 子 父。

棧模擬算法

1. 掃描字串，提取所有名字並按順序編號（1-based）。
2. 再次掃描字串，維護一個棧存儲當前路徑的節點編號：
   - 遇到名字（且下一字符非字母）→ 為新節點，若棧非空，輸出 棧頂 當前編號（下行），壓入棧。
   - 遇到 , 或 ) → 彈出棧頂（回溯），若棧非空，輸出 彈出節點 新棧頂（上行）。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

char str[1000005], name[105];
char names[50005][105];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        int len = strlen(str);
        int n = 0, pos = 0;
        bool inName = false;
        // 提取名字
        for (int i = 0; i < len; ++i) {
            if (str[i] >= 'a' && str[i] <= 'z') {
                name[pos++] = str[i];
                inName = true;
            } else {
                if (inName) {
                    name[pos] = '\0';
                    strcpy(names[n++], name);
                    pos = 0;
                    inName = false;
                }
            }
        }
        if (inName) { name[pos] = '\0'; strcpy(names[n++], name); }

        printf("%d\n", n);
        for (int i = 0; i < n; ++i) printf("%s\n", names[i]);

        stack st;
        int cur = 1;
        for (int i = 0; i < len; ++i) {
            if (str[i] == '(') continue;
            if (str[i] >= 'a' && str[i] <= 'z' &&
                (i+1 >= len || str[i+1] < 'a' || str[i+1] > 'z')) {
                if (!st.empty()) printf("%d %d\n", st.top(), cur);
                st.push(cur++);
            }
            if (str[i] == ',' || str[i] == ')') {
                printf("%d ", st.top()); st.pop();
                printf("%d\n", st.top());
            }
        }
        putchar('\n');
    }
    return 0;
}

複雜度與細節

• 時間 O(L)，L 為字串長度（≤ 1,000,000）。
• 空間 O(N)，N 為節點數（≤ 50,000）。
• 注意輸入可能包含單個名字（無括號），需正確處理。
• 每組測試數據後輸出空行。