問題一覧 > 通常問題

No.1796 木上のクーロン

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : NachiaNachia / テスター : NyaanNyaanNyaanNyaan
0 ProblemId : 5373 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 00:00:12

問題文

$N$ 頂点の無向木があります。頂点には $1$ から $N$ までの番号が振られています。辺 $i$ $(1 \leq i \leq N-1)$ は頂点 $u_i$ と頂点 $v_i$ を結びます。

$2$ 頂点 $u,v$ 間の単純パスに含まれる辺の個数を $\text{dist}(u,v)$ と表します。

$k_0=(N!)^2$ とします。

$p=1,2, \ldots ,N$ について、非負整数 $E_p$ を次の式で定義します。

$E_p = \begin{align} \sum_{i=1}^{N} \frac{k_0Q_i}{(\text{dist}(p,i)+1)^2} \end{align}$

$p=1,2, \ldots ,N$ について、 $E_p$ の値を $998244353$ で割った余りを求めてください。

入力

入力は以下の形式で与えられます。

$N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $2 \leq N \leq 200000$
  • $1 \leq u_i \lt v_i \leq N$
  • $0 \leq Q_i \leq 998244352$

出力

$N$ 行出力してください。 $p$ 行目に $E_p$ の値を $998244353$ で割った余りを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
2
1 2
1 2
出力
6
9

$k_0=(2!)^2=4$ です。

$\begin{align} E_1=\frac{4 \times 1}{1}+\frac{4 \times 2}{4}=6 \end{align}$ です。

$\begin{align} E_2=\frac{4 \times 1}{4}+\frac{4 \times 2}{1}=9 \end{align}$ です。

サンプル2
入力
5
8 9 10 11 12
1 2
1 3
1 4
4 5
出力
242400
202800
215600
260800
242300

サンプル3
入力
15
384021089 193015378 976219268 137749749 349176187 734053188 898423703 796747226 1930431 466001235 375378632 199170540 856435845 150579368 391611266
1 11
9 11
7 11
7 12
2 12
3 12
7 13
4 13
10 13
6 13
10 14
5 14
5 15
8 15
出力
164992737
231041473
448643960
643742276
843736071
249725816
936586510
118229251
332387563
883236064
929035671
219161259
34328230
192575536
139074045

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。