PROBLEM LINK: Problem
Author and editorialist: Denis Anishchenko
Tester: Hasan Jaddouh
DIFFICULTY: Medium
PREREQUISITES: DFS, constructive
EXPLANATION:
Let’s denote root of the tree is the first vertex (rooted tree). Let’s consider the deepest leaf v and his parent p. We must associate edge (v, p) for some triple. If vertex p has only one child that the answer is ‘NO’ because we can’t associate edge (v, p). If vertex p has two childs than we can definitely get triple (p, parent(p)), (p, v), (p, v') , where v' - another child of p. If vertex p has more or equal than 3 child that means we can get one arbitrary triple. So, we can on each iteration consider deepest leaf and take one triple in a current answer, or say that is impossible. We can keep set of neighbors and priority queue for depth of each vertex. So, we have O(n \log{n}) solution. (Exists solution in O(n) too)