원심분리기

당신은 최근 은하 간 폐기물 수거 임무에서 버려진 미래형 로봇을 발견했다. 이 로봇은 내부에 유체가 든 공 모양의 관절 $n$개로 이루어져 있다. 관절들은 $n-1$개의 유연한 파이프로 연결되어 있고, 파이프를 따라 유체가 양방향으로 흐를 수 있다. 이 유체를 분석하려고 원심분리기를 사용하기로 했다.

원심분리기 사용법은 잘 모르기 때문에, 관절 하나를 원심분리기의 중심에 고정하고 기계를 켰다. 기계가 빠르게 회전하면 모든 유체가 중심에서 바깥쪽으로 밀려난다. 유체가 흐를 수 있는 파이프가 둘 이상이면, 유체는 그 파이프들에 균등하게 나뉜다.

과정이 끝났을 때 가장 바깥쪽 관절에 유체가 얼마나 남는지 궁금하다. 어느 관절을 중심에 고정했는지 잊어버렸으므로, 관절을 무작위로 골랐다고 가정하고 각 관절에 남는 유체의 기댓값을 구해야 한다.

첫 줄에 관절의 수 $n$ ($1 \leq n \leq 2 \cdot 10^5$)이 주어진다.

다음 줄에는 $i$번 관절의 유체 양 $a_i$ ($0 \leq a_i \leq 10^9$)가 $n$개 주어진다.

다음 $n-1$개의 줄에는 파이프로 연결된 두 관절 $u$, $v$ ($1 \leq u, v \leq n$)가 주어진다. 이 파이프들은 트리를 이룬다.

$n$개의 줄에 정수를 하나씩 출력한다. $i$번째 줄은 과정이 끝난 뒤 $i$번 관절에 남는 유체 양의 기댓값을 $998\,244\,353$으로 나눈 나머지이다.

형식적으로, $M = 998\,244\,353$이라 하자. 답은 기약분수 $\frac{p}{q}$로 나타낼 수 있으며 $q \not\equiv 0 \pmod{M}$이다. $0 \le x < M$이고 $x \cdot q \equiv p \pmod{M}$을 만족하는 정수 $x$를 출력한다.

첫 번째 예시에서 1번 관절을 중심에 고정하면 모든 유체가 1번에서 2번으로 흐르고, 합쳐진 유체가 3번으로 흐른다. 따라서 1번과 2번은 비고, 3번에 7단위의 유체가 모인다.

2번 관절을 중심에 고정하면 유체의 절반은 1번으로, 절반은 3번으로 흐른다. 각 관절에는 순서대로 2, 0, 5단위가 남는다. 3번 관절을 고정하면 7단위 전부가 1번에 남는다.

각 관절의 유체 기댓값은 다음과 같다. $\frac{1}{3} \cdot (0 + 2 + 7) = 3$ $\frac{1}{3} \cdot (0 + 0 + 0) = 0$ $\frac{1}{3} \cdot (7 + 5 + 0) = 4$