{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\\(N\\) islands are floating on the sea, connected by \\(N-1\\) wooden bridges. If we consider each island as a vertex and each bridge as an edge, these \\(N\\) islands and \\(N-1\\) bridges form a tree.\u003c/p\u003e\n\n\u003cp\u003eDreamGrid is taking a walk among the islands through the wooden bridges, and he will start his walk on a random island with equal probability. But beware, these bridges are out of repair for long years! Let\u0027s denote the durability of the \\(i\\)-th bridge as \\(d_i\\). Every time DreamGrid passes a bridge (in either direction), its durability will be decreased by 1. If the durability is reduced to 0, the wooden bridge will break into pieces and DreamGrid can never walk across it again.\u003c/p\u003e\n\n\u003cp\u003eBut DreamGrid is busy brainstorming the problems for the next monthly and is not aware of the danger. During his walk, he will select a bridge connecting his current position with equal probability and walk pass it (thus moving to another island). This procedure will be repeated until DreamGrid finds himself stuck on an island. Poor DreamGrid.\u003c/p\u003e\n\n\u003cp\u003eBut we are not interested in rescuing DreamGrid (even if this leads to the postponement of the next monthly). What we are interested in is that, what\u0027s the expected number of times he passes a bridge before he is stuck. Please write a program to solve this problem.\u003c/p\u003e\n\n\u003cp\u003eRecall that a tree is an undirected connected graph with \\(N\\) vertices and \\(N-1\\) edges.\n\n\u003c/p\u003e\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer \\(T\\) (\\(1 \\le T \\le 40\\)), indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains an integer \\(N\\) (\\(1 \\le N \\le 10\\)), indicating the number of islands.\u003c/p\u003e\n\n\u003cp\u003eThe following \\(N-1\\) lines each contains three integers \\(u_i\\), \\(v_i\\) and \\(d_i\\) (\\(1 \\le u_i, v_i \\le n\\), \\(1 \\le d_i \\le 15\\)), indicating a bridge connecting island \\(u_i\\) and island \\(v_i\\) with a durability of \\(d_i\\).\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the given graph is a tree.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line, indicating the expected number of times DreamGrid passes a bridge before he is stuck.\u003c/p\u003e\n\n\u003cp\u003eYour answer will be considered correct if its absolute or relative error is not larger than \\(10^{-9}\\).\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\n4\n1 2 1\n1 3 1\n1 4 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.416666666666667\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003eRoute\u003c/th\u003e\u003cth\u003eProbability\u003c/th\u003e\u003cth\u003e# of Times to\u003cbr\u003eCross a Bridge\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e1 - 2\u003c/td\u003e\u003ctd\u003e1/12\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1 - 3\u003c/td\u003e\u003ctd\u003e1/12\u003c/td\u003e\u003ctd\u003e1\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1 - 4 - 1 - 2\u003c/td\u003e\u003ctd\u003e1/24\u003c/td\u003e\u003ctd\u003e3\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1 - 4 - 1 - 2\u003c/td\u003e\u003ctd\u003e1/24\u003c/td\u003e\u003ctd\u003e3\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2 - 1 - 3\u003c/td\u003e\u003ctd\u003e1/8\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2 - 1 - 4 - 1 - 3\u003c/td\u003e\u003ctd\u003e1/8\u003c/td\u003e\u003ctd\u003e4\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3 - 1 - 2\u003c/td\u003e\u003ctd\u003e1/8\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3 - 1 - 4 - 1 - 2\u003c/td\u003e\u003ctd\u003e1/8\u003c/td\u003e\u003ctd\u003e4\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4 - 1 - 2\u003c/td\u003e\u003ctd\u003e1/12\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4 - 1 - 3\u003c/td\u003e\u003ctd\u003e1/12\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4 - 1 - 4\u003c/td\u003e\u003ctd\u003e1/12\u003c/td\u003e\u003ctd\u003e2\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n font-size: 14px;\n}\n\u003c/style\u003e\n"}}]}