[問題案] Tree Distance Sum

[NachiaVivias]

Problem name: Tree Distance Sum (Optional) Problem ID: tree_distance_sum

問題文

辺重みつきの $N$ 頂点の木、長さ $N$ の数列 $A$ が与えられるので、各頂点 $v$ について $\sum_{u} A_u \text{dist}(u,v)\pmod{998 244 353}$ を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1\leq A_i,W_i\leq 998 244 352$

想定解

#172

全方位木DP

入力

N
A[0] A[1] ...
U[0] V[0] W[0]
U[1] V[1] W[1]
:

出力

ans[0] ans[1] ... ans[N-1]

note

頂点と辺の情報を無視する問題設定だともったいないと思ったので、重みをつけました。

どうせ入出力が遅いし、制約はこだわらなくてもよさそうです。