Kirito in Memeland

Memeland is a country consisting of N cities. There are exactly N - 1 undirected roads connecting pairs of cities and there is exactly one path between each pair of cities (a path is a sequence of distinct cities where consecutive cities in the sequence are connected by a road). As the country is located in mountains, cities may be at different heights. The heigh of i-th city is ai. Kirito is go