P10706 Sorrow (Sorrow)

>$$You are an angel,$$ > >$$descending amid light and holy hymns.$$ > >$$I am a demon,$$ > >$$crawling out of blood and filthy mud.$$ > >$$I want to hold you,$$ > >$$but I fear my blood$$ > >$$will stain your pure white wings red.$$

Given a tree with $n$ nodes rooted at node $1$. Each node has two weights $a_i, b_i$ ($1 \le i \le n$). The values $a_i$ are given, and all $b_i$ are initially $0$. Now, for every pair of nodes $(u, v)$ ($1 \le u < v \le n$), let $x = \operatorname{LCA}(u, v)$. If $\gcd(a_u, a_v) > 1$, then set $b_x \gets b_x + a_u \times a_v$; otherwise, do nothing. For each $1 \le i \le n$, output $b_i \bmod 998244353$.

The first line contains an integer $n$, meaning there are $n$ nodes. The second line contains $n$ positive integers, representing $a_1, a_2, \dots, a_n$. The next $n - 1$ lines each contain two positive integers $u, v$, indicating there is an edge between node $u$ and node $v$.

Output $n$ lines, each containing one integer. The $i$-th line should be the value of $b_i$ modulo $998244353$.

#### Sample Explanation  The constructed tree is shown in the figure. The following contributions exist: - For node $1$: $(3, 4)$ contributes $4$. $(3, 5)$ contributes $4$. $(3, 7)$ contributes $144$. $(3, 8)$ contributes $48$. $(1, 6)$ contributes $9$. $(1, 7)$ contributes $216$. $(1, 8)$ contributes $72$. $(6, 7)$ contributes $216$. $(6, 8)$ contributes $72$. Total: $785$. - For node $4$: $(4, 5)$ contributes $4$. $(4, 7)$ contributes $144$. $(4, 8)$ contributes $48$. $(5, 8)$ contributes $48$. $(7, 8)$ contributes $1728$. Total: $1972$. - For node $5$: $(5, 7)$ contributes $144$. Total: $144$. All other nodes are clearly $0$. #### Constraints | Subtask ID | $n$ | $a_i$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $100$ | $\le 1000$ | $-$ | $5$ | | $1$ | $2000$ | $\le 10^5$ | $-$ | $10$ | | $2$ | $10^5$ | $\le 5 \times 10^5$ | $A$ | $25$ | | $3$ | $2 \times 10^5$ | $\le 5 \times 10^5$ | $B$ | $30$ | | $4$ | $2 \times 10^5$ | $\le 5 \times 10^5$ | $-$ | $30$ | Special property $A$: it is guaranteed that all $a_i$ are generated randomly. Special property $B$: it is guaranteed that the tree is a complete binary tree. For $100\%$ of the testdata: $1 \le n \le 2 \times 10^5$, $1 \le a_i \le 5 \times 10^5$. **Special note: This problem uses bundled subtask testing. You will only get the score for a subtask if you pass all test points in that subtask.** Translated by ChatGPT 5