TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

World of Goo is a puzzle game with a strong emphasis on physics, for WiiWare, Windows, Mac OS X, and Linux (x86 and x86-64) by 2D Boy, an independent game developer consisting of Kyle Gabler and Ron Carmel, both former Electronic Arts employees. It was nominated for the Seumas McNally grand prize, Design Innovation Award and Technical Excellence at the Independent Games Festival. It was released for the Wii's WiiWare service in North America on 13 October 2008. On 11 November 2008, 2D Boy announced that World of Goo would be released as WiiWare in Europe in lieu of a retail release. During the 2009 D.I.C.E. Summit, Nintendo announced that it would publish World of Goo in Japan during the second quarter of 2009; the game was released on 21 April 2009 under the title Planet of Goo. On 24 March 2009, it was announced that World of Goo would be part of the MacHeist III bundle. On 13 October 2009, the first anniversary of the game's release, 2D Boy announced a one-week offer (which was later extended until 25 October 2009) on their blog where people could pay whatever amount they liked to buy the game. They also posted the results of this sale on their blog where 22% of buyers paid only to support the Pay-What-You-Want model. A demo version of the WiiWare version was released on November 20, 2009.

The game is built around the idea of creating large structures using balls of goo. The game is divided into five chapters, each containing several levels. Each level has its own graphic and musical theme, giving it unique atmosphere, similar in style to Tim Burton's film designs. There is also a bonus meta-game called World of Goo Corporation, where the objective is to build the highest tower using goo balls which the player collected through the course of the game. Players from all over the world can compete, as the height of the tower and number of goo balls used is being constantly uploaded to the 2D Boy server.

This time, the game becomes a little special. The goos do not want to build a high tower; instead, they want to occupy the largest amount of resource. The n (1<= n<=1000) resource points, numbered from 1 to n, each of which has a resource value, are connected by exactly n-1 pipes so that each resource point can reach every other resource point through a path composed of pipes and resource points. And there are m goos (1<= m<=100; m<= n), each of which can occupy exactly one resource point. What's more, if m>1, the m goos must stay together as no goo wants to stay alone or in a relatively small group, which means each goo can reach every other goo through a path composed of pipes and resource points occupied by goos.

Input Format

In the first line, one integer shows the number of test cases.
For each test case, two integers n and m, the number of resource points and the number of goos, is given.
Following line has n integers indicate the resource value of each point.
Each of the n integers can fit in a 32-bits signed integer.
Then there comes n-1 lines, each of which contains two integers, p and q, standing for a pipe connecting two resource points numbered p and q.

Output Format

For each test case, output the largest resource value the goos can occupy.

Sample Input 1

2
3 1
1 2 3
1 2
2 3

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

Sample Output 1

3
5

Hints

Problem Source

Migrated from old NTUJ.

2010 yg ChuHai

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 262144 6