{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eIt is well known that Keima Katsuragi is The Capturing God because of his exceptional skills and experience in \u0027\u0027capturing\u0027\u0027 virtual girls in gal games. He is able to play $k$ games simultaneously.\u003cbr\u003e\u003cbr\u003eOne day he gets a new gal game named \u0027\u0027XX island\u0027\u0027. There are $n$ scenes in that game, and one scene will be transformed to different scenes by choosing different options while playing the game. All the scenes form a structure like a rooted tree such that the root is exactly the opening scene while leaves are all the ending scenes. Each scene has a value , and we use $w_i$ as the value of the $i$-th scene. Once Katsuragi entering some new scene, he will get the value of that scene. However, even if Katsuragi enters some scenes for more than once, he will get $w_i$ for only once.\u003cbr\u003e\u003cbr\u003eFor his outstanding ability in playing gal games, Katsuragi is able to play the game $k$ times simultaneously. Now you are asked to calculate the maximum total value he will get by playing that game for $k$ times.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$($T \\le 20$), denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two numbers $n, k(1 \\le k \\le n \\le 100000)$, denoting the total number of scenes and the maximum times for Katsuragi to play the game \u0027\u0027XX island\u0027\u0027.\u003cbr\u003e\u003cbr\u003eThe second line contains $n$ non-negative numbers, separated by space. The $i$-th number denotes the value of the $i$-th scene. It is guaranteed that all the values are less than or equal to $2^{31} - 1$.\u003cbr\u003e\u003cbr\u003eIn the following $n - 1$ lines, each line contains two integers $a, b(1 \\le a, b \\le n)$, implying we can transform from the $a$-th scene to the $b$-th scene.\u003cbr\u003e\u003cbr\u003eWe assume the first scene(i.e., the scene with index one) to be the opening scene(i.e., the root of the tree).\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output \u0027\u0027Case #t:\u0027\u0027 to represent the $t$-th case, and then output the maximum total value Katsuragi will get.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n5 2\r\n4 3 2 1 1\r\n1 2\r\n1 5\r\n2 3\r\n2 4\r\n5 3\r\n4 3 2 1 1\r\n1 2\r\n1 5\r\n2 3\r\n2 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 10\r\nCase #2: 11\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}