{"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 众所周知,Matt 是ACM-ICPC中一个出色的参赛者。图问题是他最喜欢的。\u003cbr\u003e\u003cbr\u003e 有一次,他不小心想出了一种在树中找到最大独立集的简单算法。\u003cbr\u003e\u003cbr\u003e 树是一个无环连通无向图,独立集是顶点集的子集,其中不包含相邻的顶点对。\u003cbr\u003e\u003cbr\u003e 假设树包含N个顶点,方便地用1,2,...,N编号。首先,Matt 随机均匀地选择一个{1, 2, 3, ..., N}的排列p\u003csub\u003e1\u003c/sub\u003e, p\u003csub\u003e2\u003c/sub\u003e, ..., p\u003csub\u003eN}。\u003cbr\u003e\u003cbr\u003e 在选择排列后,Matt 进行以下过程。\u003cbr\u003e\u003cbr\u003e 1.设置 S \u003d \u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/68ad011154eda8d33baebe99940851c4?v\u003d1717740643\"\u003e.\u003cbr\u003e 2.相应地考虑顶点p\u003csub\u003e1\u003c/sub\u003e, p\u003csub\u003e2\u003c/sub\u003e, ..., p\u003csub\u003eN\u003c/sub\u003e。对于顶点p\u003csub\u003ei\u003c/sub\u003e,如果且仅如果S中没有与p\u003csub\u003ei\u003c/sub\u003e相邻的顶点,则将顶点p\u003csub\u003ei\u003c/sub\u003e添加到S中。\u003cbr\u003e 3.输出集合S。\u003cbr\u003e\u003cbr\u003e 显然,上述算法并不总是输出最大独立集。Matt 想知道集合S的期望大小。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"第一行只包含一个整数T,表示测试用例的数量。\u003cbr\u003e\u003cbr\u003e 对于每个测试用例,第一行包含一个整数N (1 ≤ N ≤ 200),表示图中顶点的数量。\u003cbr\u003e\u003cbr\u003e 接下来的N - 1行中,每行包含两个整数u, v (1 ≤ u, v ≤ N),表示u和v之间有一条边。您可以假设所有顶点都是相连的。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行“Case #x: y”,其中x是案例编号(从1开始),y是答案。为避免四舍五入误差,您应输出的答案是:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e(独立集的期望大小) × N! mod (10\u003csup\u003e9\u003c/sup\u003e + 7)\u003c/center\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\u003e2\r\n4\r\n1 2\r\n1 3\r\n1 4\r\n3\r\n1 2\r\n2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 60\r\nCase #2: 10\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"在第一个示例中,有4个顶点,所以Matt可能得到4!种排列。\u003cbr\u003e假设Matt得到的排列是1 2 3 4。他将顶点1添加到独立集中。\u003cbr\u003e假设Matt得到的排列是2 1 3 4。他将顶点2、顶点3和顶点4添加到独立集中。\u003cbr\u003e显然,如果排列中的第一个元素不是顶点1,他将得到大小为3的独立集。否则,他将得到大小为1的独立集。由于有18种排列的第一个元素不是顶点1,所以第一个示例的答案是(3 × 18 + 1 × 6) mod (10^9 + 7) \u003d 60。\u003cbr\u003e"}}]}