CF 29D：Ant on the Tree - 樹的遍歷與葉子順序約束

問題描述

給定一棵樹 (根為 1)，需從根出發遍歷所有節點並返回根，每條邊恰好走兩次。且葉子節點必須按給定順序訪問。求可行路徑或判斷無解 (-1)。

核心觀察

在樹上「每條邊走兩次」的遍歷本質是 DFS 順序。葉子順序約束等價於要求 DFS 訪問葉子的順序與給定順序一致。

構造方法：依次連接 1 → leaf[1] → leaf[2] → ... → leaf[k] → 1 的最短路徑，拼接起來。若拼接後總長度 = 2*(n-1) (即 2n-1 個節點)，則合法；否則無解。

算法步驟

1. 預處理：BFS/DFS 求每節點父節點與深度，支持 LCA 或直接回溯路徑。
2. 定義 get_path(u, v) 返回從 u 走到 v 的節點序列 (含 u，不含 v 的父方向重複部分)。
3. 路徑構造：ans = get_path(1, leaf[0])；對每個 i，ans += get_path(leaf[i], leaf[i+1])；最後 ans += get_path(leaf[k-1], 1)。
4. 若 ans.size() == 2*n - 1 輸出，否則 -1。

代碼關鍵片段

vector get_path(int u, int v) {
    // 返回 u 到 v 的路徑節點 (不含 v 為避免重複)
    // 先上升到 LCA，再下降
}

int main() {
    // 讀入樹，構建父數組、深度
    // 讀入葉子順序
    vector route = {1};
    for (int i = 0; i < k; ++i) {
        int u = (i==0 ? 1 : leaf[i-1]);
        int v = leaf[i];
        auto p = get_path(u, v);
        route.insert(route.end(), p.begin(), p.end());
    }
    auto p = get_path(leaf[k-1], 1);
    route.insert(route.end(), p.begin(), p.end());
    if (route.size() == 2*n - 1) output(route);
    else cout << -1;
}

關鍵點

• 路徑拼接去重：get_path(u,v) 返回從 u 到 v 的節點序列，不含 v，避免拼接時重複。
• 判斷合法性：總長度必須為 2n-1 (每條邊兩次，共 2(n-1) 步，2n-1 個節點)。
• 樹上路徑唯一，LCA 可用倍增或簡單回溯 (n≤300)。

總結

樹上指定葉子順序的 Euler Tour 構造。利用樹上路徑唯一性，拼接相鄰葉子間路徑，驗證總長度是否符合 Euler Tour 特徵。