Help in understanding the question Triple-tree decomposition TREE3 from LTIME59

I can’t understand this question from LTIME59… Can someone please explain the question giving some more test cases!

Question: You need to divide the edges of the given tree in groups of 3, in such a way, that all the 3 edges in a particular group shares a common vertex. The edges joining vertices (1, 3), (3, 7) & (9, 3) can form a group because the vertex 3 is common. However, the edges (1, 3), (3, 5) and (1, 7) can’t form a group for the same reason. If it is impossible to group all the edges, print “NO”

Approach: Observe that the edges joining the leaf nodes can only share the other vertex (ie, the parent of that leaf node), because the leaf node itself has no other edge incident on it. Using this property, you can start from any leaf node and form groups as you go up the tree.

There are a lot of successful submissions for the problem. You can refer them. After all, the algorithm is simple:- keep on grouping the edges from one end. If you encounter any edge that can’t be grouped, exit and print “NO”.

You can refer to my solution here. I have performed a BFS and climbed up the tree gradually. However, there are easier and cleaner codes already submitted.

@admin The editorial link is not working. Please look into the matter.

1 Like

Thanks for reminder. I forgot to track this case due to exams. Will resolve this with @admin in morning.

Thanks for explanation.