Centrifuge

Interview

Time limit1.5sMemory limit2048 MB

Summary

Given a tree with fluid in each node, find each node's expected final fluid when a random node is the center and fluid flows outward, mod 998244353.

Level: Medium5 of 10
Topics: Tree, DFS, Math
Solved: No attempts yet

Problem

On your latest intergalactic scavenger trip, you discovered an abandoned futuristic robot. The robot consists of $n$ ball-shaped joints with fluid inside. These joints are connected by $n-1$ flexible pipes that let the fluid flow in both directions. To analyze the fluid, you decide to use a centrifuge.

You have no idea how to operate a centrifuge, so you fix one joint to its center and turn the machine on. The machine spins quickly, and all the fluid is pushed from the center toward the outside. Whenever fluid has more than one pipe to flow through, it splits evenly among those pipes.

You want to know how much fluid remains in the outermost joints when the process ends. You forgot which joint you fixed to the center, so assume the joint was chosen uniformly at random. Compute the expected amount of fluid in each joint.

Input

The first line contains one integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ), the number of joints.

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 each contain two integers $u$ and $v$ ( $1 \leq u, v \leq n$ ), meaning there is a pipe between joint $u$ and joint $v$ . These pipes form a tree.

Output

Output $n$ lines with one integer each. The $i$ -th line is the expected amount of fluid in joint $i$ after the process, modulo $998\,244\,353$ .

Formally, let $M = 998\,244\,353$ . The answer can be written as an irreducible fraction $\frac{p}{q}$ with $q \not\equiv 0 \pmod{M}$ . Output the integer $x$ with $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$ .

Hint

In the first sample, if joint 1 is fixed at the center, all fluid flows from joint 1 to joint 2, and the combined fluid flows to joint 3. In total, joints 1 and 2 are empty, and all 7 units of fluid are at joint 3.

If joint 2 is fixed at the center, half of its fluid flows to joint 1 and half to joint 3. The joints then hold 2, 0, and 5 units. If joint 3 is fixed, all 7 units end up at joint 1.

The expected amounts are: $\frac{1}{3} \cdot (0 + 2 + 7) = 3$ $\frac{1}{3} \cdot (0 + 0 + 0) = 0$ $\frac{1}{3} \cdot (7 + 5 + 0) = 4$

Examples2

Example 1
Input
```
3
1 2 4
1 2
2 3
```
Expected output
```
3
0
4
```

Example 2

Input

6
4 1 3 11 7 2
1 4
2 3
6 2
2 4
4 5

Expected output