提示: 欢迎访问OurACM平台。
Problem 2083 洞穴照明

Accept: 68    Submit: 360
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

shadow酷爱探险,这次shadow来到了一个洞穴中,他发现这个幽深的洞穴由一些房间(相对较为宽敞的区域)和连接这些房间的通道构成,它们形成了一个树形结构。当shadow探索完整个洞穴出来后,他觉得这里可以作为一个旅游景点来开发,但首先他必须解决这个洞穴中的照明问题。由于这个洞穴中的通道都较为笔直,因而在洞穴中的任意房间建立照明设施都可以照亮与其直接相连的所有房间,但在每个房间建立照明设施所需的费用又因地形不同而不同,所以shadow想知道要照亮整个洞穴所需的最少费用是多少。

Input

输入第一行一个整数T( T <= 50),表示有T组数据。

每组数据第一行是一个整数n( 0 < n <= 50000 ),表示这个洞穴中有n个房间,房间编号从1开始。

接下来n行,每行一个整数,其中第i行的整数wi ( 0 < wi <= 10000 )表示在第i个房间建立照明设施所需的费用为wi。

接下来n-1行,每行两个整数a,b ( 1 <= a,b <= n )表示房间a和房间b之间有一条通道相连,数据保证所给的是一棵树。

Output

对于每组数据输出一行,包含组数和照亮整个洞穴所需的最少费用,详细格式参见样例输出。

Sample Input

1 5 3 4 5 1 2 1 2 1 3 2 4 2 5

Sample Output

Case 1: 6

Source

FOJ有奖月赛-2012年4月(校赛热身赛)

Submit  Back  Status  Discuss