{"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\"\u003eN children are living in a tree with exactly N nodes, on each node there lies either a boy or a girl.\u003cbr\u003eA girl is said to be protected, if the distance between the girl and her nearest boy is no more than D.\u003cbr\u003eYou want to do something good, so that each girl on the tree will be protected. On each step, you can choose two nodes, and swap the children living on them.\u003cbr\u003eWhat is the minimum number of steps you have to take to fulfill your wish?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line has a number T (T \u0026lt;\u003d 150) , indicating the number of test cases.\u003cbr\u003eIn a case, the first line contain two number n (1 \u0026lt;\u003d n \u0026lt;\u003d 50), D (1 \u0026lt;\u003d D \u0026lt;\u003d 10000000), Which means the number of the node and the distance between the girls and boys.\u003cbr\u003eThe next lines contains n number. The i\u003csub\u003eth\u003c/sub\u003e number means the i\u003csub\u003eth\u003c/sub\u003e node contains a girl or a boy. (0 means girl 1 means boy), The follow n - 1 lines contains a, b, w, means a edge connect a\u003csub\u003eth\u003c/sub\u003e node and b\u003csub\u003eth\u003c/sub\u003e node, and the length of the edge is w (1 \u0026lt;\u003d w \u0026lt;\u003d 10000000)."}},{"title":"Output","value":{"format":"HTML","content":"For every case, you should output \"Case #t: \" at first, without quotes. The \u003ci\u003et\u003c/i\u003e is the case number starting from 1.\u003cbr\u003eThen follows the answer, -1 meas you can\u0027t comlete it, and others means the minimum number of the times."}},{"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\n3 1\r\n0 0 1\r\n1 2 1\r\n1 3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}