No.1796 Coulomb on a Tree
タグ : / 解いたユーザー数 11
作問者 : 👑
Nachia
/ テスター :
NyaanNyaan
Problem Statement
There is an undirected tree with $N$ vertices. The vertices are numbered from $1$ to $N$. Edge $i$ $(1 \leq i \leq N-1)$ connects vertex $u_i$ and vertex $v_i$.
For $2$ vertices $u,v$, let $\text{dist}(u,v)$ denote the number of edges contained in the simple path between them.
Let $k_0=(N!)^2$.
For $p=1,2, \ldots ,N$, define the non-negative integer $E_p$ by the following formula.
$ \begin{aligned} E_p = \sum_{i=1}^{N} \frac{k_0Q_i}{(\text{dist}(p,i)+1)^2} \end{aligned} $
For $p=1,2, \ldots ,N$, find the value of $E_p$ modulo $998244353$.
Input
The input is given in the following format.
$N$
$Q_1$ $Q_2$ $\ldots$ $Q_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
The input satisfies the following constraints.
- All input values are integers
- $2 \leq N \leq 200000$
- $1 \leq u_i \lt v_i \leq N$
- $0 \leq Q_i \leq 998244352$
Output
Print $N$ lines. On line $p$, print the value of $E_p$ modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
2 1 2 1 2
Output
6 9
We have $k_0=(2!)^2=4$.
We have $\begin{aligned} E_1=\frac{4 \times 1}{1}+\frac{4 \times 2}{4}=6 \end{aligned}$.
We have $\begin{aligned} E_2=\frac{4 \times 1}{4}+\frac{4 \times 2}{1}=9 \end{aligned}$.
Sample 2
Input
5 8 9 10 11 12 1 2 1 3 1 4 4 5
Output
242400 202800 215600 260800 242300
Sample 3
Input
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
Output
164992737 231041473 448643960 643742276 843736071 249725816 936586510 118229251 332387563 883236064 929035671 219161259 34328230 192575536 139074045
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。