Sponsored
Sponsored
Use these hints if you're stuck. Try solving on your own first.
Root the tree at node <code>0</code>.
If a leaf node is not divisible by <code>k</code>, it must be in the same component as its parent node so we merge it with its parent node.
If a leaf node is divisible by <code>k</code>, it will be in its own components so we separate it from its parent node.
In each step, we either cut a leaf node down or merge a leaf node. The number of nodes on the tree reduces by one. Repeat this process until only one node is left.