Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Observation 1: Ari should teleport to one of the attacked cities (it doesn't worth going to a city that is not attacked since then she should go to one of the attacked cities)
- Observation 2: The nodes visited by Ari will determine a sub-tree T of the original tree, this tree is unique and is determined by all the paths from two attacked cities.
- Observation 3: If Ari had to return to the city from where she started, then the total distance would be 2e, where e is the number of edges of T, that is because she goes through each edge forward and backward
- Observation 4: If Ari does not have to return to the starting city (the root of T), then the total distance is 2e - L, where L is the distance of the farthest node from the root
- Observation 5: In order to get a minimum total distance, Ari should chose one diameter of the tree, and teleport to one of its leaves.
- The problem is now transformed in finding the diameter of a tree that contains the smallest index for one of its leaves. Note that all diameters pass through the center of the tree, so we can find all the farthest nodes from the center...and [details omitted].
Add Comment
Please, Sign In to add comment
