This is my solution to this problem Restore Graph. I have used an approach which seems similar to that suggested in the editorial (which I translated from Russian) but I can't really understand it. Here's what I have done
1) Created a HashMap that maps distances from roots to nodes. For example, if I put in map, it will give me a list of nodes that are at distance 1 from the root.
2) Start from the root vertex for which D[start] = 0. I do a DFS search from the root. For each node, which is at distance dist, I check for neighbours that are at distance dist + 1 and visit only k of them if not already visited. Each time I visit another node, I add (current_node, neighbour) to the answer set.
3) That's about it. At the end, I check if the size of the visited map is not equal to n, then output -1. Otherwise I output the answers.
I am getting TLE on the 7th test case which has a considerable input size and I am using Java 8. Is my algorithm too slow or is it because of the language?