P10808 [LMXOI Round 2] Annihilation

LMX 和 HQZ 在研究上次被毙掉的题目 Impacter 时，他们提出了一个新的问题。

给定一棵 $n$ 个节点的，以 $1$ 为根的树，每个点有权值 $a_i$。 对于一个点 $u$，定义函数 $f(u,v,d)$ 表示在 $u$ 的子树内选择一些点（至少需要选取一个点），选出的点中最大权值为 $v$，且它们编号的最大公约数为 $d$ 的方案数。 给定一个常数 $k$ 和一个序列 $b$，对于每个点 $u$，你需要求出 $ \sum\limits_{k|i}^{n}\sum\limits_{j=1}^nf(u,i,j)\times b_j$ 的值，其中 $k|i$ 表示 $k$ 可以整除 $i$。由于该值可能很大，所以你需要输出其对 $998244353$ 取模的结果。

无

无

**样例解释 #1** 节点 $3$ 可以选择 $\{3\}$，因为是求最大值为 $1$ 的倍数，所以贡献为 $2$。 节点 $2$ 可以选择 $\{2\},\{3\},\{2,3\}$，因为是求最大值为 $1$ 的倍数，所以贡献是 $1+2+1=4$ 。 节点 $1$ 可以选择 $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$，因为是求最大值为 $1$ 的倍数，所以贡献是 $1+1+2+1+1+1+1=8$ 。 对于所有数据，$1 \le a_i\le n\le 10^5$，$1\le b_i\le 10^9$。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :--------: | :----------------: | :------------: | :--: | | Subtask #1 | $\le 20$ | 无 | $10$ | | Subtask #2 | $\le 200$ | 无 | $10$ | | Subtask #3 | $\le 2000$ | 无 | $10$ | | Subtask #4 | $\le 10^5$ | 树随机生成* | $10$ | | Subtask #5 | $\le 10^5$ | $k=1$ | $20$ | | Subtask #6 | $\le 5\times 10^4$ | 无 | $20$ | | Subtask #7 | $\le 10^5$ | 无 | $20$ | 树随机生成*：指对于 $u=2,3,\ldots n$ 每个点，其父亲从 $[1,u-1]$ 的整数中均匀随机选取。