Collecting Cherries in a Tree
A Step-by-Step Explanation with Diagrams
1 Problem Restatement (Plain Language)
We are given a rooted tree with:
• n vertices numbered 1 to n
• Root at vertex 1
• Every leaf contains exactly one cherry
We want to collect all cherries using the following operation:
• Choose any vertex v and shake it
• All cherries in leaf descendants of v fall
• If a cherry falls twice, the tree breaks (forbidden)
• The total number of shakes must be a multiple of 3
Question: Is it possible to collect all cherries safely?
2 Key Observations
2.1 Observation 1: Each leaf must be shaken exactly once
Each cherry must fall exactly once. Therefore:
• Every leaf must be covered by exactly one shake
• Shakes define a partition of leaves
2.2 Observation 2: Shaking a node covers all leaves in its subtree
If we shake a node v, we collect:
all cherries in the subtree rooted at v
So each shake corresponds to choosing a subtree.
1
2.3 Observation 3: Only the number of shakes modulo 3 matters
The problem only asks whether the number of shakes is:
0 (mod 3)
Exact number does not matter, only its remainder modulo 3.
3 High-Level Strategy
We use:
• Tree DP
• DFS traversal
• Modulo 3 arithmetic
At each node, we compute:
• Which remainders modulo 3 are possible for the number of shakes in its subtree
4 DP State Definition
For each node x, define:
1
if it is possible to collect all cherries in subtree of x
dp[x][r] = using a number of shakes ≡ r (mod 3)
0 otherwise
where r ∈ {0, 1, 2}.
5 Base Case: Leaves
A leaf has exactly one cherry.
• If we shake the leaf itself, we use exactly one shake
• So for a leaf:
dp[leaf] = [0, 1, 0]
This matches the initialization in the code:
dp = vector<vector<int>>(n, vector<int>{0, 1, 0});
2
6 Tree Combination Idea
When processing an internal node:
• We combine results from its children
• Each child contributes a possible remainder modulo 3
• Combining two subtrees adds their shake counts modulo 3
This is a convolution modulo 3.
7 Combining Subtrees (Core Logic)
Suppose:
r[k] = possible remainders from processed children
For a child y:
dp[y][j] = 1 ⇒ j is possible
New remainder:
(k + j) mod 3
This is implemented as:
nr[(k+j)%3] += r[k];
8 Why Start With r = [1,0,0]
Before processing any children:
• Zero shakes is possible
• Zero modulo 3 remainder
So:
r = [1, 0, 0]
9 DFS Transition (Step-by-Step)
1. Start DFS from root
2. For each node:
• Recursively process children
• Combine their DP states
3. After combining children:
• If remainder 0 is possible, set dp[x][0] = 1
• If remainder 2 is possible, set dp[x][2] = 1
3
10 Why Remainder 1 Is Excluded
If remainder 1 occurs at an internal node:
• We can perform an extra shake at this node
• This adds 1 shake
• Turns remainder 1 into 2, or 2 into 0
Thus remainder 1 is never needed to propagate upward.
This explains:
if(r[0]) dp[x][0] = 1;
if(r[2]) dp[x][2] = 1;
11 Leaf Optimization
This code:
if(p != -1 && adj[x].size()==1) return;
Means:
• If node is a leaf (degree 1, not root)
• Its DP is already initialized
• No need to process further
12 Visual Example
1
2 3
4 5
Leaves: 3, 4, 5
Each leaf contributes remainder 1.
We combine bottom-up and check if root can achieve remainder 0.
13 Final Decision
After DFS:
Answer = YES if dp[1][0] = 1
Implemented as:
cout << (dp[0][0] ? "YES" : "NO") << "\n";
4
14 Time and Space Complexity
• Each edge processed once
• Each DP combination is constant work
Time Complexity = O(n)
Space Complexity = O(n)
15 Final Intuition Summary
• Each leaf needs exactly one shake
• Internal nodes combine shake counts
• Only modulo 3 matters
• Tree DP + modulo arithmetic solves the problem
Elegant, fast, and optimal.