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.
A valid set of shaken vertices is a cover of the leaves where no leaf is covered twice. That means chosen subtrees must be disjoint on leaves.
If two chosen vertices have an ancestor-descendant relationship, they overlap on at least one leaf. So the chosen vertices form an ancestry antichain.
For a subtree rooted at , only the number of shakes modulo matters. Let be the set of possible residues for fully collecting cherries inside that subtree.
There are two cases for : shake itself, giving residue , or do not shake , meaning every child subtree must be solved independently and their residues get added modulo .
Store as a 3-bit mask. Combine children with tiny modulo- convolution, then add residue . The answer is whether residue is possible at the root.
A strategy is valid exactly when every leaf is covered by one chosen vertex and no leaf is covered twice. If we choose both a vertex and one of its descendants, then every leaf under the descendant is collected twice, so that is instantly illegal. In other words, the chosen vertices form an antichain by ancestry, and their subtrees partition the leaves.
Now root the tree at . For each vertex , define as the set of possible values of
such that all cherries in the subtree of are collected exactly once.
There are only two real choices at .
First, we can shake itself. Then all leaves below are collected in one move, so residue is possible.
Second, we can decide not to shake . Then no chosen vertex can cover leaves from two different child subtrees, because the only vertex that could do that is itself. So each child subtree must be solved independently. If the children are , then this gives all residues
where .
So for an internal vertex,
For a leaf, , because the only way to collect its cherry is to shake that leaf itself. The empty child-sum would be , but zero shakes clearly collects nothing. That fake option needs to die immediately.
Since there are only three residues, use a 3-bit mask. Bit means residue is possible. To combine children, start with residue for the empty sum, then merge each child mask by trying all residue pairs.
Correctness follows by induction on the subtree. Any valid strategy for subtree either shakes , giving exactly the first case, or it does not. If it does not, then the strategy splits cleanly among child subtrees, and the total number of shakes is the sum of their counts. The DP enumerates exactly those sums. Conversely, every DP construction either shakes once or combines valid child strategies, so it never double-collects a leaf and covers every leaf in the subtree.
Finally, the whole tree is possible iff , because the required total number of shaken vertices must be a multiple of .
The tree can be processed bottom-up with an iterative DFS order to avoid recursion depth drama on nodes.
Complexity: per test case, since every edge is processed once and each merge is constant work. Memory: .
#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>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
stack<int> st;
st.push(1);
parent[1] = -1;
while (!st.empty()) {
int v = st.top();
st.pop();
order.push_back(v);
for (int to : adj[v]) {
if (to == parent[v]) continue;
parent[to] = v;
st.push(to);
}
}
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
bool leaf = true;
int combined = 1; // only residue 0 before adding children
for (int to : adj[v]) {
if (to == parent[v]) continue;
leaf = false;
int nxt = 0;
for (int a = 0; a < 3; a++) {
if (!(combined & (1 << a))) continue;
for (int b = 0; b < 3; b++) {
if (dp[to] & (1 << b)) {
nxt |= 1 << ((a + b) % 3);
}
}
}
combined = nxt;
}
dp[v] = 1 << 1; // shake v itself
if (!leaf) dp[v] |= combined;
}
cout << ((dp[1] & 1) ? "YES" : "NO") << '\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>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> parent(n + 1, 0), order;
order.reserve(n);
stack<int> st;
st.push(1);
parent[1] = -1;
while (!st.empty()) {
int v = st.top();
st.pop();
order.push_back(v);
for (int to : adj[v]) {
if (to == parent[v]) continue;
parent[to] = v;
st.push(to);
}
}
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
bool leaf = true;
int combined = 1; // only residue 0 before adding children
for (int to : adj[v]) {
if (to == parent[v]) continue;
leaf = false;
int nxt = 0;
for (int a = 0; a < 3; a++) {
if (!(combined & (1 << a))) continue;
for (int b = 0; b < 3; b++) {
if (dp[to] & (1 << b)) {
nxt |= 1 << ((a + b) % 3);
}
}
}
combined = nxt;
}
dp[v] = 1 << 1; // shake v itself
if (!leaf) dp[v] |= combined;
}
cout << ((dp[1] & 1) ? "YES" : "NO") << '\n';
}
return 0;
}