Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Track where the cat could be, not where you hope it is. A deletion is safe only if the deleted vertex is impossible for the cat to occupy.
Color the tree like a chessboard. Every 1 operation moves across one edge, so it flips the cat's color. Deletions do not change the cat's color.
If the cat's current possible color is known, then deleting any vertex of the opposite color is always safe. The cat cannot be there, no matter how annoyingly it chose earlier moves.
Root the tree at node . If you only delete current rooted leaves, the remaining vertices always stay connected and still contain .
Keep two stacks of current leaves by color. Before each deletion, if there is no leaf of the opposite color, do one move to flip the cat's color. Then delete an opposite-color leaf, update its parent, and do one move to separate this deletion from the next one.
The main false assumption is that we can guide the cat along some exact path. We cannot. The cat chooses arbitrarily on every 1, so its exact position is nonsense. What we can control is a weaker invariant: the color of every possible position.
Root the tree at node and color every vertex by
Every edge connects opposite colors. The cat starts at node , so initially its color is
Every move operation crosses exactly one edge, so while more than one vertex remains, it flips the cat's color. A delete operation does not move the cat, so it does not change the color.
Therefore, before each deletion, if the cat's possible color is , then every vertex of color is definitely safe to delete. The cat cannot be there. No guessing, no vibes.
We want the final remaining vertex to be . So root the current remaining tree at and repeatedly delete a rooted leaf other than .
A rooted leaf has no remaining children. Since it is not the root, it has exactly one edge to the rest of the tree: its parent edge. Deleting it does not split the remaining tree. So if the cat was alive before and not on that leaf, it stays alive inside the connected component containing .
After such deletions, only node remains. Since the cat never died, it must be standing on .
Maintain:
parent[v]: parent of in the tree rooted at ;children[v]: how many not-yet-deleted children has;color: the color where the cat could currently be.Initially, compute all of these with one DFS or BFS from .
For each of the vertices we need to delete:
color.1. This flips color.color ^ 1.children[parent].1 and flip color again.That last move is important: it guarantees we never print two delete operations consecutively. It also keeps the color invariant updated for the next round.
At the start of each deletion round, fewer than vertices have been deleted, so at least two vertices remain. The remaining graph is connected and contains root , so there is at least one rooted leaf different from .
If there is already a leaf with color opposite to color, great, delete it.
Otherwise, all current leaves have color color. We output one move, the cat's possible color flips, and now those same leaves are opposite to the new color. So a valid leaf exists.
We prove the key invariant before every deletion:
color equals the color of every possible cat position.Initially this is true: the graph is the whole tree, the cat is at , and color = depth[1] % 2.
Before a deletion, the algorithm ensures the deleted vertex has color color ^ 1. Since the cat can only be on color color, the deleted vertex cannot contain the cat. So the cat survives.
The deleted vertex is a rooted leaf, so removing it does not disconnect the rest of the remaining graph. The remaining graph is still connected and still contains .
After each printed 1, if more than one vertex remains, the cat must move across one edge, so its color flips. The algorithm flips color exactly the same way. If this is the final extra move after only remains, the cat has no adjacent vertex and stays at ; there are no later deletions, so the stale color no longer matters.
Thus all deletions are safe, and after deletions only remains. The cat is alive, so it ends at .
Each deleted vertex costs:
So the total number of operations is at most
The time complexity is per test case, and the total input size is , so this is comfortably AC.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), depth(n + 1, 0), children(n + 1, 0);
vector<int> st = {n};
parent[n] = 0;
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int to : g[v]) {
if (to == parent[v]) continue;
parent[to] = v;
depth[to] = depth[v] + 1;
children[v]++;
st.push_back(to);
}
}
array<vector<int>, 2> leaves;
for (int v = 1; v <= n; v++) {
if (children[v] == 0) {
leaves[depth[v] & 1].push_back(v);
}
}
vector<pair<int, int>> ans;
ans.reserve(3 * n);
int color = depth[1] & 1;
for (int removed = 0; removed < n - 1; removed++) {
if (leaves[color ^ 1].empty()) {
ans.push_back({1, 0});
color ^= 1;
}
int v = leaves[color ^ 1].back();
leaves[color ^ 1].pop_back();
ans.push_back({2, v});
int p = parent[v];
if (p != 0) {
children[p]--;
if (children[p] == 0) {
leaves[depth[p] & 1].push_back(p);
}
}
ans.push_back({1, 0});
color ^= 1;
}
cout << ans.size() << '\n';
for (auto [type, v] : ans) {
if (type == 1) cout << "1\n";
else cout << "2 " << v << '\n';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> parent(n + 1, 0), depth(n + 1, 0), children(n + 1, 0);
vector<int> st = {n};
parent[n] = 0;
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int to : g[v]) {
if (to == parent[v]) continue;
parent[to] = v;
depth[to] = depth[v] + 1;
children[v]++;
st.push_back(to);
}
}
array<vector<int>, 2> leaves;
for (int v = 1; v <= n; v++) {
if (children[v] == 0) {
leaves[depth[v] & 1].push_back(v);
}
}
vector<pair<int, int>> ans;
ans.reserve(3 * n);
int color = depth[1] & 1;
for (int removed = 0; removed < n - 1; removed++) {
if (leaves[color ^ 1].empty()) {
ans.push_back({1, 0});
color ^= 1;
}
int v = leaves[color ^ 1].back();
leaves[color ^ 1].pop_back();
ans.push_back({2, v});
int p = parent[v];
if (p != 0) {
children[p]--;
if (children[p] == 0) {
leaves[depth[p] & 1].push_back(p);
}
}
ans.push_back({1, 0});
color ^= 1;
}
cout << ans.size() << '\n';
for (auto [type, v] : ans) {
if (type == 1) cout << "1\n";
else cout << "2 " << v << '\n';
}
}
return 0;
}