問題一覧 > 通常問題

No.2494 Sum within Components

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 173
作問者 : KumaTachiRen / テスター : shinchan
お気に入りにしたユーザー ProblemId : 9950 / 自分の提出
問題文最終更新日: 2023-10-06 21:27:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 407 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。