P7574 "PMOI-3" Subtree

There is a formal statement below the separator line, which can be used together.

b6e0 has a tree. The $i$-th node has value $a_i$. Each edge has length $1$. b6e0 will choose a node as the root, denoted by $r$. Then, b6e0 will select the entire subtree of some node as his territory, and let the root of this subtree be $u$. At this time, every node in the tree will bring b6e0 some profit. When the root of the territory subtree is $u$, the profit brought by node $x$, denoted by $f(x,u)$, is defined as follows: 1. If $x$ is in the subtree of $u$, then its profit equals the profit of its parent node plus its own value $a_x$. 2. If $x$ is not in the subtree of $u$, then its profit is: among the nodes adjacent to it, take those whose distance to $u$ (the length of the simple path to $u$) is greater than the distance from $x$ to $u$; take the maximum of these nodes' profits **modulo $998244353$**, and then multiply it by $a_x$. With root $r$, define the profit of taking $u$ as the subtree, $W(u)$, as the sum of $f$ over all nodes. Of course, b6e0 has many ways to choose the root. Define the profit when choosing $r$ as the root, $C(r)$, as the sum over all $u$ of the subtree profit $W(u)$. For each node $r$, compute $C(r)$. --- Formal statement: You are given a tree with $n$ nodes. The $i$-th node has weight $a_i$, and each edge has length $1$. When the root is $r$: Let $F(x)$ denote the parent of $x$. In particular, $F(r)=0$. Let $D(x,y)$ denote the length of the simple path from $x$ to $y$. In particular, for all $x$, $D(x,x)=0$. Let $A_x$ denote the set of nodes in the subtree of $x$ (including $x$ itself), i.e. $A_x=\{y\mid D(x,y)=D(F(x),y)-1\}$. In particular, $A_r=\{1,2,\cdots,n\}$. Let $B_x$ denote the set of nodes adjacent to $x$, i.e. $B_x=\{y\mid D(x,y)=1\}$. Define $f(x,u)$: $$f(x,u)=\begin{cases}f(F(x),u)+a_x&x\in A_u\\a_x\cdot\max_{y\in B_x,D(y,u)>D(x,u)}\{f(y,u)\bmod 998244353\}&x\not\in A_u\end{cases}$$ In particular, for all $x$, $f(0,x)=0$. In the case $x\not\in A_u$, if for all $y\in B_x$ we have $D(y,u)\le D(x,u)$, then $f(x,u)=a_x$. Define the score of node $u$ as $W(u)=\sum_{v=1}^nf(v,u)$. Define the profit of node $r$, $C(r)$, as the value of $\sum_{i=1}^nW(i)$ when the root is $r$. For each node $r$, compute $C(r)$. **All $C(r)$ are taken modulo $998244353$.**

The first line contains a positive integer $n$, the number of nodes in the tree. The second line contains $n$ integers. The $i$-th integer denotes the node weight $a_i$ of node $i$. The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is an edge between node $u$ and node $v$.

Output $n$ lines. The $i$-th line outputs a positive integer, the value of node $i$'s profit $C(i)$ **modulo $998244353$**.

[Sample Explanation] The tree in the sample is shown in the figure:  For example, when $r=1$ and $u=5$, $f(2,u)=a_2=2$, $f(1,u)=a_1\cdot f(2,u)=14$, $f(3,u)=a_3\cdot f(1,u)=70$, $f(6,u)=a_6=5$, $f(4,u)=a_4\cdot\max\{f(3,u),f(6,u)\}=7000$, and $f(5,u)=f(4,u)+a_5=7001$. [Constraints] - Subtask 1 (10 pts): $n\le200$, $a_i\le 10^3$. - Subtask 2 (20 pts): $n\le10^3$. - Subtask 3 (20 pts): the tree is a chain. - Subtask 4 (20 pts): there exists a node whose degree is $n-1$. - Subtask 5 (30 pts): no special restrictions. For $100\%$ of the testdata, $1\le n\le5\times10^5$, $1\le a_i\le10^9$. Translated by ChatGPT 5