{"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\u0027s a well-known fact that MMM, the greatest general in history, loves traveling. \u003cbr\u003eThis time she is setting off to Tianjin, a city famous for stuffed-bun, with her MMM Army. Tianjin is a city with N sites. And N sites are divided into several areas. Each site belongs to exactly one area. For each area, the number of sites and the number of street connected them are equal, and each pair of sites belong to the same area, there existed at least one simple path going from one site to the other. For each pair of sites belong to different area, no streets will connect them. The deliciousness of buns in the bakehouse on the i-th site is evaluated as an integer Wi. As MMM wants to maintain Bureaucratic Government (BG for short) to her army, she would invite them to every bakehouse on their way. But there is one problem: MMM hates to visit a site twice because 2 is an ominous number to her. However, they could choose to take the subway if in need. The subway in Tianjin is well developed so they can transport from any sites to any other sites conveniently even if when they are not connected by the streets. But MMM will feel carsick if they take the subway K times or more.\u003cbr\u003eNow the question is, what\u0027s the maximum total deliciousness can MMM reach without carsickness? Note that with the convenient subway the MMM Army can start and end their journey in any site.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input consist of one integer T which means T cases will follow (1≤T≤15).\u003cbr\u003eThen follow T cases, each case begin with two integers N, K (1≤ N ≤ 50000, 1≤ K ≤10).\u003cbr\u003eThe following line contains N integer Wi, |Wi| ≤ 10^6.\u003cbr\u003eThen N line follow, each line contains two integer u, v. mean there is a street between site u and site v. 1 ≤ u, v ≤ N\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"Just a line contains the maximum total deliciousness"}},{"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\u003e1\r\n9 3\r\n-2 -10 3 15 11 1 10 10 -3\r\n1 2\r\n1 3\r\n2 3\r\n2 4\r\n2 5\r\n5 6\r\n3 7\r\n8 9\r\n9 8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003emmm\u0027s army start at city 6, and walk to city 4,the path is 6-\u0026gt;5-\u0026gt;2-\u0026gt;4. total deliciousness is 1+11+(-10)+15\u003d17.\u003cbr\u003ethen take subway to city 3, and then walk to city 7,the path is 3-\u0026gt;7. total deliciousness is 3+10\u003d13.\u003cbr\u003ethen take subway to city 8, and end their travel at city 8.total deliciousness is 10,\u003cbr\u003eso the answer is 17+13+10\u003d40.\u003cbr\u003e\u003cbr\u003e"}}]}