TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4104
  • 题目
  • P4104FarmCraft
    限制 : 时间限制 : 50000 MS   空间限制 : 165536 KB
    问题描述

    In a village called Byteville, there are  houses connected with  roads. For each pair of houses, there is a unique way to get from one to another. The houses are numbered from 1 to . The house no. 1 belongs to the village administrator Byteasar. As part of enabling modern technologies for rural areas framework,  computers have been delivered to Byteasar's house. Every house is to be supplied with a computer, and it is Byteasar's task to distribute them. The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers.

    Byteasar has loaded all the computers on his pickup truck and is about to set out to deliver the goods. He has just the right amount of gasoline to drive each road twice. In each house, Byteasar leaves one computer, and immediately continues on his route. In each house, as soon as house dwellers get their computer, they turn it on and install FarmCraft. The time it takes to install and set up the game very much depends on one's tech savviness, which is fortunately known for each household. After he delivers all the computers, Byteasar will come back to his house and install the game on his computer. The travel time along each road linking two houses is exactly 1 minute, and (due to citizens' eagerness to play) the time to unload a computer is negligible.

    Help Byteasar in determining a delivery order that allows all Byteville's citizens (including Byteasar) to start playing together as soon as possible. In other words, find an order that minimizes the time when everyone has FarmCraft installed.

    输入格式

    The first line of the standard input contains a single integer  () that gives the number of houses in Byteville. The second line contains  integers  (), separated by single spaces;  is the installation time (in minutes) for the dwellers of house no. .

    The next  lines specify the roads linking the houses. Each such line contains two positive integers  and  (), separated by a single space. These indicate that there is a direct road between the houses no.  and .

    You may assume that in tests worth  of the total points, the condition  holds.

    输出格式

    The first and only line of the standard output should contain a single integer: the (minimum) number of minutes after which all citizens will be able to play FarmCraft together.

    样例输入

    6
    1 8 9 6 3 2
    1 3
    2 3
    3 4
    4 5
    4 6

    样例输出

    11

    提示

    Byteasar should deliver the computers to the houses in the following order: 3, 2, 4, 5, 6, and 1. The game will be installed after 11, 10, 10, 10, 8, and 9 minutes respectively, in the house number order. Thus everyone can play after 11 minutes.

    If Byteasar delivered the game in the following order: 3, 4, 5, 6, 2, and 1, then the game would be installed after: 11, 16, 10, 8, 6, and 7 minutes respectively. Hence, everyone could play only after 16 minutes,


    来源  poi2014 bzoj3829