| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 2048 MB | 0 | 0 | 0 | 0.000% |
On your latest intergalactic scavenger trip, you discovered an abandoned futuristic robot. Mysteriously, the robot consists of $n$ ball-shaped joints with some kind of fluid inside. These joints are all connected together via $n-1$ flexible pipes that allow the fluid to flow bidirectionally from one joint to another. To analyze this strange fluid inside the robot, you decide to use a centrifuge.
Since you have no clue how to actually use a centrifuge, you secure one of the joints to the center of it and turn the machine on. The machine then rapidly spins around the center, and all the fluids are pushed away from the center towards the outside. Whenever the fluid has more than one pipe to flow through, the fluid splits evenly between all of these pipes.
You wonder how much fluid will be in the outermost joints at the end of this process. After thinking so much, you forgot which joint you secured to the center. Therefore, you have to calculate the expected amount of fluid in each joint as if you chose a joint at random.
The first line contains one integer $n$ (1ドル \leq n \leq 2 \cdot 10^5$) --- the number of joints of the robot.
The next line contains $n$ integers $a_i$ (0ドル \leq a_i \leq 10^9$) --- the amount of fluid in the $i$-th joint.
The next $n-1$ lines contain two integers $u$ and $v$ (1ドル \leq u, v \leq n$) --- indicating a pipe between joint $u$ and $v$. These pipes form a tree.
Output $n$ lines with one integer per line, the $i$-th representing the expected amount of fluid in the $i$-th joint after the process modulo 998ドル,244円,353円$.
Formally, let $M = 998,244円,353円$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q},ドル where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that 0ドル \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
3 1 2 4 1 2 2 3
3 0 4
6 4 1 3 11 7 2 1 4 2 3 6 2 2 4 4 5
928921837 0 818005794 0 679360751 568444705
In the first sample, if the first joint is fixed at the center, all fluid will flow from joint 1ドル$ to 2ドル,ドル and the combined fluid will flow to joint 3ドル$. In total, joint 1ドル$ and 2ドル$ will be empty, and all 7ドル$ units of fluid will be at joint 3ドル$.
If the second joint is fixed to the center, half of its fluid will flow to 1ドル$ and half will flow to 3ドル$. There will be 2ドル,ドル 0ドル,ドル and 5ドル$ units of fluid at each joint respectively. If joint 3ドル$ is fixed, all 7ドル$ units of fluid will be at joint 1ドル$.
In total, the expected amount of fluid in each joint is
$\frac{1}{3} \cdot (0 + 2 + 7) = 3$
$\frac{1}{3} \cdot (0 + 0 + 0) = 0$
$\frac{1}{3} \cdot (7 + 5 + 0) = 4$