给定一棵大小为 \(n\) 的树，需要构造不超过 \(3n\) 条指令（有以下两种，且不能有连续两次 \(2\) 操作），使得一个在 \(1\) 的棋子一定能走到 \(n\)。
- \(1\)，表示棋子会移动到一个和它相邻的节点，没有则不移动。
- \(2 \ u\)，表示摧毁节点 \(u\) 及其邻边，需保证棋子不在 \(u\)。
\(1h\)
首先如何保证进行而操作时棋子不在 \(u\) ?
有一种自然的想法，因为树是一种二分图，按照深度的奇偶性分成两个集合，只需要保证此前执行的 \(1\) 操作次数的奇偶性与 \(u\) 的深度不一样即可。
我们应该先将除 \(1 \rightarrow u\) 的点先删干净。因为每次删一个叶子不会使棋子与 \(n\) 处于两个连通块内，所以优先删叶子节点，即深度较大的点。假设执行 \(c\) 次一操作，就删深度奇偶性为 \((c \& 1) \oplus 1\) 中最大的点即可，如果没有可以进行一操作然后再删深度为 \(c \& 1\) 的点，显然每个点不会花费超过 \(3\) 次操作。
对于路径上的点，先保证棋子不在 \(u\)，即至少在 \(u\) 的儿子（通过至多一次 \(1\) 操作办到），然后删去 \(u\)，再挪棋子即可。
时间复杂度：\(O(n)\)。