树上游走 (1s,512M)

小王在一棵树上随机游走。

具体来说，假设小王在点 $pos$ ，那么他将在下一步等概率随机选择一条一端为 $pos$ 的边，并走到其另一个端点。

你希望小王尽可能快的走到点 $1$ ，因此你希望通过一些手段，令其第一次到达点 $1$ 的时间的期望尽可能短。

小王走每条边所花费的时间均为 $1$ 。而你可以做的手段为，在小王到达某个点时，告诉小王接下来不要走若干条边。若如此做，则他下一步将在你没说的边集中等概率随机一条走过去。（你要至少要留一条边给小王选择走）

当然，你如果做上述过程也是需要花费代价的，如果你在某一时刻告诉了小王 $k$ 条边不能走，你又需要花费 $a_k$ 时间来让小王理解。（ $a_0=0$ ，保证 $a_i\leq a_{i+1}$ ）

注意：小王的记忆力并不是很好。即使你在某一时刻在点 $X$ 告诉小王了一些边，小王下一次到达点 $X$ 时还会忘掉你之前所说的，如果还想如此做则需再花费一遍代价。

你需要对 $2\sim n$ 中的每个点求出小王首次到达 $1$ 号点的最小期望时间。

答案对 $998244353$ 取模。

输入第一行一个整数 $n$ 。第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$ 。接下来 $n-1$ 行每行两个整数，表示树上的一条边连接的两个端点。

输出一行 $n-1$ 个整数，表示对于点 $2,3,\ldots,n$ 的答案。

对于所有数据，保证 $n\leq 5\times 10^5, a_i\leq 10^9$ 。

在下列比赛中:

#2503. 树上游走