問題一覧 > 通常問題

No.2949 Product on Tree

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 92
作問者 : nouka28 / テスター : rotti_coder aplysiaSheep t9unkubj
お気に入りにしたユーザー ProblemId : 11081 / 自分の提出
問題文最終更新日: 2024-10-18 06:37:01
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 451 (並木中等プログラミングコンテスト 2024) (順位表) の他の問題:

Problem Statement

You are given a sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$ of length $N$ and a tree with $N$ vertices. The vertices are numbered from $1$ to $N$, and the $i$-th edge connects vertices $U_i,V_i$.

The cost $f(i,j)$ between $2$ distinct vertices $i,j$ is defined as follows.

  • Let $p_1(=i),p_2,\dots,p_k(=j)$ be the vertices on the simple path connecting vertices $i,j$, in order, where $k$ is the number of vertices on the path. Then, $f(i,j)=A_{p_1}\times A_{p_2} \times \dots \times A_{p_k}$.

Find $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ modulo $998244353$.

Constraints

  • $2\leq N\leq 2\times 10^5$
  • $0\leq A_i< 998244353$
  • $1\leq U_i,V_i\leq N$
  • All input values are integers.
  • The given graph is a tree.

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

Output

Print $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$ modulo $998244353$.

Sample

Sample 1
Input
4
1 2 3 4
1 2
2 3
2 4
Output
54

There are the following $6$ paths to consider.

  • $f(1,2)=1\times 2=2$
  • $f(1,3)=1\times 2\times 3=6$
  • $f(1,4)=1\times 2\times 4=8$
  • $f(2,3)=2\times 3=6$
  • $f(2,4)=2\times 4=8$
  • $f(3,4)=3\times 2\times 4=24$

The answer is $54$, which is the remainder when $2+6+8+6+8+24=54$ is divided by $998244353$.

Sample 2
Input
2
0 0
1 2
Output
0

Sample 3
Input
10
810284561 609063208 909877398 113848143 744347504 567699714 418423327 541843429 325332295 953873148
10 6
5 10
2 5
4 2
9 6
3 10
8 3
7 10
1 6
Output
318883473

Print the answer modulo $998244353$.

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