No.2494 Sum within Components
タグ : / 解いたユーザー数 173
作問者 :
shinchan
Problem Statement
There is a simple undirected graph $G$ with $N$ vertices and $M$ edges, where the $i\ (1\leq i\leq M)$-th edge connects vertices $U_i,V_i$. Each vertex also has an integer written on it, and the number written on vertex $i\ (1\leq i\leq N)$ is $A_i$.
Find the product of the answers to the following problem for each of $x=1,2,\dots,N$, modulo $998244353$.
- Problem: Find the sum of the integers written on all vertices connected to vertex $x$.
Input
$N\ M$ $A_1\ A_2\ \dots\ A_N$ $U_1\ V_1$ $U_2\ V_2$ $\vdots$ $U_M\ V_M$
- $1\leq N\leq 2\times 10^5$
- $0\leq M\leq \min\left(2\times 10^5,\frac{N(N-1)}{2}\right)$
- $0\leq A_i\lt 998244353$
- $1\leq U_i\lt V_i\leq N$
- If $i\neq j$, then $(U_i,V_i)\neq(U_j,V_j)$
- All inputs are integers
Output
Output the required value on $1$ line. End the output with a newline.
Sample
Sample 1
Input
3 1 3 1 2 1 2
Output
32
The answers are as follows, so the required value is $4\times 4\times 2=32$.
- The vertices connected to vertex $1$ are vertices $1,2$, and the sum of the integers written on them is $3+1=4$.
- The vertices connected to vertex $2$ are vertices $1,2$, and the sum of the integers written on them is $3+1=4$.
- The vertex connected to vertex $3$ is vertex $3$, and the sum of the integers written on it is $2$.
Sample 2
Input
5 3 100 200 300 400 500 1 4 2 5 3 4
Output
230959687
Output the value modulo $998244353$.
Sample 3
Input
10 7 133 136 161 196 236 251 251 352 512 585 1 6 2 8 2 10 3 6 4 5 5 7 8 10
Output
314159265
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。