410575: GYM104053 I Infection

A highly propagating bacterium infects a tree of $$$n$$$ nodes (with $$$n-1$$$ edges, no cycles). These nodes are indexed from $$$1$$$ to $$$n$$$.

Exactly one node will be infected at the beginning. Each node on the tree has an initial susceptibility weight $$$a_i$$$, which represents that node $$$i$$$ has a probability of $$$\dfrac{a_i}{\sum_{i=1}^{n}a_i}$$$ to become the initial infected node of the tree.

In addition, each node has an infection probability $$$p_i$$$, which represents its probability of being infected by adjacent nodes.

Specifically, starting from the initial infected node, if a node is infected, the uninfected node $$$x$$$ that is adjacent to it will have a probability of $$$p_x$$$ to become a new infected node, and then $$$x$$$ can continue to infect its adjacent nodes.

Now, your task is to calculate the probability that exactly $$$k$$$ nodes are eventually infected. You need to output an answer for each $$$k=1,\ldots, n$$$.

You need to output the answer modulo $$$10^9+7$$$, which means if your answer is $$$\frac{a}{b}$$$ ($$$\gcd(a,b)=1$$$), you need to output $$$a\cdot b^{-1}\bmod{10^9+7}$$$, where $$$b\cdot b^{-1} \equiv 1 \pmod{10^9+7}$$$.

The first line contains an integer $$$n$$$ ($$$2\leq n \leq 2\,000$$$), denoting the number of nodes of the tree.

The next $$$n-1$$$ lines, each line contains two positive integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v\leq n$$$), denoting that there is an edge $$$(u,v)$$$ on the tree.

Next $$$n$$$ lines, the $$$i$$$-th line contains three positive integers $$$a_i, b_i, c_i$$$, where $$$a_i$$$ means as above and $$$p_i=\frac{b_i}{c_i}$$$. It is guaranteed that $$$1\leq a_i, b_i, c_i \leq 10^9, \displaystyle \sum_{i=1}^{n}a_i\leq 10^9, b_i\leq c_i, \gcd(b_i,c_i)=1$$$.

Output $$$n$$$ lines, each line contains single integer. The integer on the $$$i$$$-th line should be the answer modulo $$$10^9+7$$$ when $$$k=i$$$.

5
2 1
5 2
3 2
4 3
2 1 5
3 1 2
2 1 1
2 1 1
3 1 2

208333335
166666668
166666668
950000007
508333337