CF29D Ant on the Tree

题目知识点：LCA。

题目传送门

题意

给定一棵以 \(1\) 为节点的树，再给定树的所有叶子节点的一个序列。

现在执行一个操作：从 \(1\) 开始遍历每个节点，并返回根，要求每条边经过的次数一定为 \(2\) 。

问是否能够使得访问节点序列中叶子节点的序列符合给定序列的条件下，满足上述操作的条件。

思路

我们暂时不考虑每条边经过次数一定为 \(2\) 的这个要求，先看我们一定要经过的点。

• 对于给定序列的第一个和最后一个，由于要求需要从根节点出发和回到根节点，因此，这两个的路径有一端点是根节点；
• 对于序列中的 \(v_i\) 和 \(v_{i+1}\) 节点，由于树的特性，其路径一定为 \(v_i \to lca(v_i, v_{i+1}) \to v_{i+1}\) 。

这样，我们可以确定在满足序列的条件下，有且只有一种走法。

若出现不满足的条件，我们需要判断一下这个唯一的走法是否对于树上每条边都是走了 \(2\) 次，只需要对路径记录一下每条边访问的次数，最后检查一下即可。

实现

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::vector adj(n, std::vector<std::pair<int,int>>{});
    for (int i = 0; i < n - 1; i ++) {
        int u, v;
        std::cin >> u >> v;
        u --; v --;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    std::vector<int> dep(n, -1), fa(dep), top(dep), siz(dep), son(dep), fa_eid(dep);
    int m = 0;
    auto dfs1 = [&](auto &self, int from, int come_eid) -> void {
        siz[from] = 1;
        son[from] = -1;
        bool have_vis = false;
        for (auto [to, eid] : adj[from]) {
            if (dep[to] == -1) {
                have_vis = true;
                dep[to] = dep[from] + 1;
                fa[to] = from;
                fa_eid[to] = eid;
                self(self, to, eid);
                siz[from] += siz[to];
                if (son[from] == -1 || siz[to] > siz[son[from]]) {
                    son[from] = to;
                }
            }
        }
        m += !have_vis;
    };
    auto dfs2 = [&](auto &self, int from, int link_top) -> void {
        top[from] = link_top;
        if (son[from] == -1) return;
        self(self, son[from], link_top);
        for (auto [to, eid] : adj[from]) {
            if (to != son[from] && to != fa[from]) {
                self(self, to, to);
            }
        }
    };
    dep[0] = 0;
    dfs1(dfs1, 0, -1);
    dfs2(dfs2, 0, 0);

    auto GetLca = [&](int a, int b) -> int {
        while (top[a] != top[b]) {
            if (dep[top[a]] < dep[top[b]]) {
                std::swap(a, b);
            }
            a = fa[top[a]];
        }
        if (dep[a] > dep[b]) {
            std::swap(a, b);
        }
        return a;
    };

    std::vector<int> vis_cnt(n - 1);
    std::vector<int> ans;
   
    std::vector<int> ls(m);
    for (auto &item : ls) {
        std::cin >> item;
        item --;
    }

    std::vector<int> tmp;
    auto GetList = [&](auto &list, int now, int tag) {
        list.clear();
        do {
            list.emplace_back(now);
            if (fa_eid[now] != -1) vis_cnt[fa_eid[now]] ++;
            now = fa[now];
        } while (now != tag);
        list.emplace_back(tag);
   };
    GetList(tmp, ls.front(), 0);

    auto AddList = [&](auto &ret, auto &ls, bool rev) {
        if (rev) std::reverse(ls.begin(), ls.end());
        while (!ls.empty()) {
            ret.emplace_back(ls.back());
            ls.pop_back();
        }
    };
    AddList(ans, tmp, false);

    for (int i = 1; i < ls.size(); i ++) {
        int pre = ls[i - 1], now = ls[i];
        auto lca = GetLca(pre, now);
        GetList(tmp, pre, lca);
        AddList(ans, tmp, true);
        GetList(tmp, now, lca);
        AddList(ans, tmp, false);
    }
    GetList(tmp, ls.back(), 0);
    AddList(ans, tmp, true);

    if (!all_of(vis_cnt.begin(), vis_cnt.end(), [](auto item) { return item == 2; })) {
        std::cout << -1 << '\n';
    } else {
        ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
        for (auto item : ans) {
            std::cout << item + 1 << ' ';
        }
        std::cout << '\n';
    }
}