Background

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

Problem Description

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$.

Input Format

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 Format

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

3 1
1 2
2 3
1 1 2
1 1 2

8 4 2

4 1
1 2
2 4
1 3
1 1 2 1
1 2 3 1

19 5 3 1

10 3
1 2
1 3
2 4
2 5
3 6
3 7
7 8
5 9
9 10
1 3 7 3 6 6 6 9 4 8 
450163553 649444963 324825063 696619525 758594756 594697697 750550965 907640826 118301481 755848673 

475170649 914027313 64013204 696619525 210513956 594697697 111866638 907640826 0 0

Hint

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$.

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