P10808 [LMXOI Round 2] Annihilation

While studying the previously rejected problem Impacter, LMX and HQZ came up with a new problem.

Given a rooted tree with $n$ nodes, rooted at $1$, each node has a weight $a_i$. For a node $u$, define the function $f(u,v,d)$ as the number of ways to select some nodes (at least one node must be selected) within the subtree of $u$, such that the maximum weight among the selected nodes is $v$, and the greatest common divisor of their indices is $d$. Given a constant $k$ and a sequence $b$, for each node $u$, you need to compute the value of $ \sum\limits_{k|i}^{n}\sum\limits_{j=1}^nf(u,i,j)\times b_j$, where $k|i$ means that $k$ divides $i$. Since this value may be very large, output it modulo $998244353$.

The first line contains two integers $n,k$. The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between $u$ and $v$. The next line contains $n$ numbers, where the $i$-th number represents $a_i$. The next line contains $n$ numbers, where the $i$-th number represents $b_i$.

Output one line with $n$ integers, where the $u$-th integer (for $u=1,2,\ldots n$) is the answer modulo $998244353$.

**Sample Explanation #1** Node $3$ can choose $\{3\}$. Since we are summing over maximum values that are multiples of $1$, the contribution is $2$. Node $2$ can choose $\{2\},\{3\},\{2,3\}$. Since we are summing over maximum values that are multiples of $1$, the contribution is $1+2+1=4$. Node $1$ can choose $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$. Since we are summing over maximum values that are multiples of $1$, the contribution is $1+1+2+1+1+1+1=8$. For all testdata, $1 \le a_i\le n\le 10^5$, $1\le b_i\le 10^9$. | Subtask ID | $n$ | Special Property | Score | | :--------: | :----------------: | :--------------: | :---: | | Subtask #1 | $\le 20$ | None | $10$ | | Subtask #2 | $\le 200$ | None | $10$ | | Subtask #3 | $\le 2000$ | None | $10$ | | Subtask #4 | $\le 10^5$ | Random tree generation* | $10$ | | Subtask #5 | $\le 10^5$ | $k=1$ | $20$ | | Subtask #6 | $\le 5\times 10^4$ | None | $20$ | | Subtask #7 | $\le 10^5$ | None | $20$ | Random tree generation*: for each node $u=2,3,\ldots n$, its parent is chosen uniformly at random from the integers in $[1,u-1]$. Translated by ChatGPT 5