题目名称 2238. 游戏内测
输入输出 gamebeta.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 常庆卫 2016-04-15
开放分组 全部用户
提交状态
分类标签
通过:9, 提交:35, 通过率:25.71%
Gravatar咸鱼二号 100 1.328 s C++
Gravatarsui 100 1.576 s C++
GravatarAglove 100 1.710 s C++
Gravatar阿狸 100 1.893 s C++
Gravatarlxtgogogo 100 1.903 s C++
Gravatarbhiaibogf 100 2.177 s C++
GravatarKZNS 100 2.465 s C++
GravatarSatoshi 100 2.832 s C++
GravatarWAHT 100 3.271 s C++
Gravatarsui 90 1.502 s C++
关于 游戏内测 的讨论
233,似乎会爆栈...
Gravatarbhiaibogf
2016-04-15 21:02 1楼

2238. 游戏内测

★★★☆   输入文件:gamebeta.in   输出文件:gamebeta.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

某个土豪游戏招聘了N位游戏高手参与最新款游戏的内测。这N位游戏高手被安排进了N栋豪华别墅,这N栋别墅由N-1条道路连接成了一个联通图,显然,这片别墅区的连接方式应该是一棵树。

小x作为内测组组长,在1号别墅,现在他拿到了最新版的游戏,且要给其他N-1分发最新版的游戏,为了保密,游戏公司禁止通过网络传输游戏安装包,小x必须要骑单车给其他人送安装光盘。    

小x从一个别墅走到另一个别墅花费的时间为1分钟。一旦小x到了第i个别墅,他会立即把游戏光盘交给第i个人,第i个人会以迅雷不及掩耳之势开始安装,这两步因为很迅速,时间可以忽略,但是因为游戏内测要有普遍性,这N位游戏高手使用的电脑配置并不相同,第i台电脑安装游戏需要花费的时间为Ci。还是避免泄密,游戏公司要求每条道路小x最多只能经过两次。

小x必须给其他人送完游戏光盘后,回到自己的别墅才能开始安装自己那份游戏。

现在问,小x如何合理安排送光盘的顺序,使得N个人安装完游戏花费的时间最短,并计算这个时间。

【输入格式】

第一行一个整数N

第二行,N个用空格分开的整数,Ci表示第i个别墅安装游戏更新需要的时间。

接下来N-1行,每行两个整数Xi和Yi,表示别墅Xi和别墅Yi之间有一条道路相连。

保证Xi和Yi在[1..N]之间

【输出格式】

一行 一个整数

【样例输入】

6

1 8 9 6 3 2

1 3

2 3

3 4

4 5

4 6

【样例输出】

11

【提示】


小x送游戏的顺序应该是3,2,4,5,6.每个房间安装好游戏的时间为11,10,10,10,8,9。

【数据范围】

  40%  N<=7000

  100%  2<=N<=500000  Ci在[1..10^9]之间



【来源】

在此键入。