A6008. 收缩的树
编程题
提高+/省选-
知识点
题目描述
给定一棵 $n$ 个点的树，节点编号为 $1$ 到 $n$ ；每次从剩余的边中等概率随机选择一条边删除并合并它连接的两个节点（合并方法是，等概率（即 $1/2$ ）选择其中一个节点，将剩余的与它相连边的这一端连到另一个节点上，最后删除选择的节点），直到树上只剩下唯一的一个节点；现在你需要计算每个节点成为最终剩余的这个节点的概率；概率对 $10^9+7$ 取模。
输入格式
第一行一个正整数 $n$ 代表树上的节点数，紧接着 $n-1$ 行每行两个正整数 $a_i$ 和 $b_i$ 表示一条连接 $a_i $ 与 $ b_i$ 的边。保证输入是一棵树， $1 \leq n \leq 500, 1 \leq a_i,b_i \leq n$ 。
输出格式
一行 $ n $ 个非负整数分别表示每个节点成为最终剩余节点的概率取模后的结果，每两个数间以一个空格分隔。
输入输出样例
输入 #1
4 1 2 1 3 1 4
输出 #1
125000001 291666669 291666669 291666669
输入 #2
7 1 2 2 3 3 4 4 5 5 6 6 7
输出 #2
467773441 982421882 485351566 128906251 485351566 982421882 467773441
输入 #3
7 1 5 1 2 2 4 2 3 3 6 4 7
输出 #3
937239590 849609381 937239590 937239590 112890626 112890626 112890626
说明/提示
| 测试点 | $n$ | 特殊约定 |
| :-: | :-: | :-: |
| $1$ | $18$ | 数据随机生成 |
| $2$ | $18$ | 树退化为链 |
| $3$ | $100$ | 无 |
| $4$ | $100$ | 树退化为链 |
| $5$ | $300$ | 数据随机生成 |
| $6$ | $300$ | 无 |
| $7$ | $300$ | 无 |
| $8$ | $500$ | 树退化为链 |
| $9$ | $500$ | 无 |
| $10$ | $500$ | 无 |
| :-: | :-: | :-: |
| $1$ | $18$ | 数据随机生成 |
| $2$ | $18$ | 树退化为链 |
| $3$ | $100$ | 无 |
| $4$ | $100$ | 树退化为链 |
| $5$ | $300$ | 数据随机生成 |
| $6$ | $300$ | 无 |
| $7$ | $300$ | 无 |
| $8$ | $500$ | 树退化为链 |
| $9$ | $500$ | 无 |
| $10$ | $500$ | 无 |