在一个地区有 个城市以及 条无向边，每条边的时间边权都是 ，并且这些城市是联通的，即这个地区形成了一个树状结构。每个城市有一个等级。 现在小强想从一个城市走到另一个不同的城市，并且每条边经过至多一次，同时他还有一个要求，起点和终点城市可以任意选择，但是等级必须是相同的。 但是小强不喜欢走特别远的道路，所以他想知道时间花费最小是多少。 进阶：时间复杂度，空间复杂度

输入描述:

第一行一个正整数 ，含义如题面所述。第二行  个正整数 ，代表每个城市的等级。接下来 行每行两个正整数 ，代表一条无向边。保证给出的图是一棵树。 。 。。

输出描述:

仅一行一个整数代表答案，如果无法满足要求，输出 。