Company: Microsoft
Difficulty: medium
Challenge 2: Road Reorientation There is a network with N roads and N + 1 cities. The cities are labeled with distinct integers within the range [0..N] . Roads connect the cities in such a way that there is exactly one way to travel between any two of the cities. In other words, the network forms a tree . The roads in the network are too narrow to accommodate two cars. For this reason, every road (that connects cities A and B ) is oriented in one of two possible ways: either from A to B , or from B to A . If the road is oriented from A to B , then every car traveling from B has to give way to cars traveling from A to B . This, naturally, makes traveling from A to B much faster than traveling from B to A . A big hospital was recently founded in the city labeled 0 . For that reason, the citizens have decided to rearrange the orientation of the roads so that everyone can get to the hospital as quickly as possible. This means that the trip from every city to the 0 th city should be as fast