短题解：CF2154D Catshock

· · 题解

很牛的一道题目！完美考察了树的结构性质与选手的图论基本功。

简要题意

洛谷上的题面已经挺简要了：CF2154D Catshock，同时沿用其变量名与记号。

分析

先分析一下题意。如果没有“不能有连续两条第二种指令”，题目会变得怎么样？

猫动来动去很烦，那就让猫别动了，直到除了 1 到 n 的那条链上的结点外，所有结点都删完为止。然后从上到下，让猫动一下后删了动前那个点，就逼到 n 了。

所以原问题是更难的，意味着猫会乱动。

先从乱做的想法分析难点。在树比较深的时候，确实可以赶在猫到之前，移除比较深层的结点。但是会发现，范围小时根本没有好办法判断猫的位置。

万一一刀把猫和 n 劈得不在一个连通块了，或者直接就劈在猫身上了怎么办？这就是我们要解决的两个问题。

思路

对于一棵无根树来说，除了叶子的每个点都是割点，因此只要每次把除 n 外，树的其中一个叶子剥掉，若假定猫不舒服会自己跑，那么总能逼到 n。

因此只需保证不会劈在猫身上即可。既然必要的判定是困难的，尝试寻找一些充分条件，即只要满足这个条件，猫必定不在指定结点上。

关键是，猫移动的目的地只会是相邻结点。所以需要设计这样一个条件，使得判定这个条件用到的信息，不管猫下一步走到哪个结点，信息的变化量都是相等的。

:::info[你能试着构造吗] 试着构造这样一种条件，与判定其的信息？ :::

:::success[官方题解的构造] 若猫所在结点的奇偶性，与指定结点的奇偶性不同，那么猫一定不在指定结点上。且一个结点，与其每个相邻的结点，深度的奇偶性，都是不同的。 :::

:::success[构造的实现] 于是，删除结点 u 时，仅需执行：

因此删除一个结点至多做 3 次操作，一共删除 n 个结点，操作次数不会超过 3(n - 1) \leq 3n。 :::

代码

剥叶子的过程可以使用类拓扑排序的思想——初始先把所有叶子，即度等于 1 的结点加入队列，删除一个叶子时将与该叶子相邻的结点的度减去 1，若度被减到 1，则说明它成为了新的叶子，加入队列。

注意永远不要加入 n。

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

constexpr int N = 200000 + 1;

vector<int> adj[N];
int deg[N], dep[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
    }
    memset(deg + 1, 0, sizeof(int) * n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }

    auto dfs = [](auto &&self, int u, int fa) -> void {
        for (int v : adj[u]) if (v != fa) {
            dep[v] = dep[u] + 1;
            self(self, v, u);
        }
    };
    dfs(dfs, 1, 0);

    vector<int> op;
    bool cat = false;
    auto run = [&] {
        op.push_back(0);
        cat = !cat;
    };
    auto del = [&](int p) {
        run();
        if ((dep[p] & 1) == cat) {
            run();
        }
        op.push_back(p);
    };

    queue<int> que;
    for (int i = 1; i <= n; ++i) if (i != n && deg[i] == 1) {
        que.push(i);
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        del(u);

        for (int v : adj[u]) if (v != n && --deg[v] == 1) {
            que.push(v);
        }
    }

    cout << op.size() << '\n';
    for (int i : op) {
        if (i) {
            cout << "2 " << i << '\n';
        } else {
            cout << "1\n";
        }
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时空复杂度 \Theta(n)。