{"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\"\u003e你是“星际战士”的领袖,被派遣去摧毁虫族的一个基地。这个基地建在地下,实际上是一个巨大的洞穴,由许多房间和隧道连接而成。每个房间都有一些虫子,它们的大脑隐藏在其中的一些房间里。科学家们刚刚研发出一种新武器,希望在一些大脑上进行实验。你的任务是摧毁整个基地,并尽可能多地捕获大脑。\u003cbr\u003e\u003cbr\u003e消灭所有虫子总是比捕获它们的大脑更容易。为你绘制了一张地图,标有所有房间内的虫子数量以及可能包含大脑的可能性。洞穴的结构类似于一棵树,从入口到每个房间都有一条唯一的路径。为了尽快结束战斗,你不想等待士兵清理一个房间后再前进到下一个房间,而是必须留下一些士兵在通过的每个房间内与所有虫子战斗。士兵永远不会重新进入他们之前访问过的房间。\u003cbr\u003e\u003cbr\u003e一名星际战士可以对抗20只虫子。由于你没有足够的士兵,你只能占领一些房间,让神经毒气完成其余的工作。与此同时,你应该最大化捕获大脑的可能性。为了简化问题,只需最大化所占领房间内可能包含大脑的所有可能性的总和。制定这样的计划是一项艰巨的任务。你需要计算机的帮助。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例。每个测试用例的第一行包含两个整数N(0 ≤ N ≤ 100)和M(0 ≤ M ≤ 100),分别表示洞穴中的房间数和你拥有的星际战士数量。接下来的N行给出了房间的描述。每行包含两个非负整数,分别表示房间内的虫子数量和可能包含大脑的可能性。接下来的N-1行给出了隧道的描述。每个隧道由两个整数描述,分别是它连接的两个房间的索引。房间从1开始编号,房间1是洞穴的入口。\u003cbr\u003e\u003cbr\u003e最后一个测试用例后跟着两个-1。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,表示所占领房间内可能包含大脑的所有可能性的最大总和。\u003cbr\u003e"}},{"title":"样例","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\u003e5 10\r\n50 10\r\n40 10\r\n40 20\r\n65 30\r\n70 30\r\n1 2\r\n1 3\r\n2 4\r\n2 5\r\n1 1\r\n20 7\r\n-1 -1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e50\r\n7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}