3779 . [模板題] Tree Path Composite Sum
TopCoder
Tags
Description
You are given
- a tree with $N$ vertices,
- $N$ integers $a _ 0, a _ 1, \ldots, a _ {N-1}$ ,
- $N-1$ integers $b _ 0, b _ 1, \ldots, b _ {N-2}$ , and
- $N-1$ integers $c _ 0, c _ 1, \ldots, c _ {N-2}$ .
Edge $i$ connects vertices $u _ i$ and $v _ i$ bidirectionally.
For an integer $e$ that satisfies $0 \leq e \leq N-2$ , let $f _ e(x) = b _ e x + c _ e$ .
Let $e _ 0, e _ 1, \ldots, e _ k$ be the edges on the simple path from vertex $x$ to vertex $y$ in order, and define $P(x, y) = f _ {e _ 0}(f _ {e _ 1}(\ldots f _ {e _ k}(a _ y) \ldots ))$ .
Find $q _ x = \sum _ {y=0} ^ {N-1} P(x, y)$ modulo $998244353$ for each vertex $x$ .
Input Format
$N$
$a _ 0$ $a _ 1$ $\ldots$ $a _ {N-1}$
$u _ 0$ $v _ 0$ $b _ 0$ $c _ 0$
$u _ 1$ $v _ 1$ $b _ 1$ $c _ 1$
$\vdots$
$u _ {N-2}$ $v _ {N-2}$ $b _ {N-2}$ $c _ {N-2}$
Output Format
$q _ 0$ $q _ 1$ $\ldots$ $q _ {N-1}$
Sample Input 1
8 1 2 3 4 5 6 7 8 0 1 10 1 1 2 10 1 0 3 10 1 0 4 10 0 0 5 10 1 5 6 10 0 6 7 10 1
Sample Output 1
9287 89589 895590 92471 92375 5131 42598 425185
Sample Input 2
3 1 100 10000 0 1 100000 0 1 2 100000 0
Sample Output 2
881938226 1855747 27566470
Hints
- All input are integers.
- $1 \leq N \leq 2 \times 10^ {5}$
- $0 \leq u _ i, v _ i \leq N - 1$
- $0 \leq a _ i \lt 998244353$
- $1 \leq b _ i \lt 998244353$
- $0 \leq c _ i \lt 998244353$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|