No.2949 Product on Tree
タグ : / 解いたユーザー数 92
作問者 :
rotti_coder
aplysiaSheep
t9unkubj
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もしくは右上の雲マークをクリックしてアカウントを作成してください。