A6008 | $收缩的树$

时间限制200ms

内存限制256MB

通过 / 提交0/0

题目描述

给定一棵 $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

输出 #1

125000001 291666669 291666669 291666669

输入 #2

输出 #2

467773441 982421882 485351566 128906251 485351566 982421882 467773441

输入 #3

输出 #3

937239590 849609381 937239590 937239590 112890626 112890626 112890626

C++ 编辑器

输入

输出