{"problem":{"name":"悲哀（Sorrow）","description":{"content":"给出一棵有 $n$ 个节点且以 $1$ 为根节点的树，每个节点有两个权值 $a_i,b_i$（$1\\le i\\le n$）。$a_i$ 已经给出，$b_i$ 初始为 $0$。 现在对于每一对节点 $(u,v)$（$1\\le u<v\\le n$），设 $x=\\operatorname{LCA}(u,v)$，如果 $\\gcd(a_u,a_v)>1$ 那么 $b_x\\gets b_x+a_u\\time","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10706"},"statements":[{"statement_type":"Markdown","content":"给出一棵有 $n$ 个节点且以 $1$ 为根节点的树，每个节点有两个权值 $a_i,b_i$（$1\\le i\\le n$）。$a_i$ 已经给出，$b_i$ 初始为 $0$。\n\n现在对于每一对节点 $(u,v)$（$1\\le u<v\\le n$），设 $x=\\operatorname{LCA}(u,v)$，如果 $\\gcd(a_u,a_v)>1$ 那么 $b_x\\gets b_x+a_u\\times a_v$，否则不做任何操作。\n\n对于每个 $1\\le i\\le n$ 求出 $b_i\\bmod998244353$。\n\n## Input\n\n第一行一个整数 $n$，表示有 $n$ 个节点。\n\n第二行 $n$ 个正整数，表示 $a_1,a_2\\dots a_n$。\n\n接下来 $n-1$ 行，每行两个正整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。\n\n## Output\n\n输出共 $n$ 行，每行一个整数。\n\n第 $i$ 行表示 $b_i$ 对 $998244353$ 取模后的结果。\n\n[samples]\n\n## Background\n\n>$$你是天使，$$\n>\n>$$于光与圣歌中降临。$$\n>\n>$$我是恶魔，$$\n>\n>$$从血与污泥中爬出。$$\n>\n>$$我想拥抱你，$$\n>\n>$$但是害怕血，$$\n>\n>$$染红你洁白的羽翼。$$\n\n## Note\n\n#### 【样例解释】\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/bti6350r.png)\n\n建出的树如图。\n\n有以下贡献：\n\n- 对 $1$ 号节点：\n\n$(3,4)$ 贡献 $4$。\n\n$(3,5)$ 贡献 $4$。\n\n$(3,7)$ 贡献 $144$。\n\n$(3,8)$ 贡献 $48$。\n\n$(1,6)$ 贡献 $9$。\n\n$(1,7)$ 贡献 $216$。\n\n$(1,8)$ 贡献 $72$。\n\n$(6,7)$ 贡献 $216$。\n\n$(6,8)$ 贡献 $72$。\n\n总共 $785$。\n\n- 对 $4$ 号节点：\n\n$(4,5)$ 贡献 $4$。\n\n$(4,7)$ 贡献 $144$。\n\n$(4,8)$ 贡献 $48$。\n\n$(5,8)$ 贡献 $48$。\n\n$(7,8)$ 贡献 $1728$。\n\n总共 $1972$。\n\n- 对 $5$ 号节点：\n\n$(5,7)$ 贡献 $144$。\n\n总共 $144$。\n\n其他节点显然都为 $0$。\n\n#### 【数据范围】\n\n| subtask 编号 | $n$ | $a_i$ | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $100$ | $\\le 1000$ | $-$ | $5$ |\n| $1$ | $2000$ | $\\le 10^5$ | $-$ | $10$ |\n| $2$ | $10^5$ | $\\le 5 \\times 10^5$ | $A$ | $25$ |\n| $3$ | $2 \\times  10^5$ | $\\le 5 \\times 10^5$ | $B$ | $30$ |\n| $4$ | $2 \\times  10^5$ | $\\le 5 \\times 10^5$ | $-$ | $30$ |\n\n特殊性质 $A$：保证所有的 $a_i$ 随机生成。\n\n特殊性质 $B$：保证树的形态是一棵完全二叉树。\n\n对于 $100\\%$ 的数据，$1\\le n\\le2\\times10^5$，$1\\le a_i\\le5\\times10^5$。\n\n**特别提醒：本题使用 subtask 捆绑测试，只有通过一个子任务的全部测试点才能获得此子任务的分数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10706","tags":[],"sample_group":[["8\n3 7 2 2 2 3 72 24 \n1 2\n1 3\n1 4\n4 5\n2 6\n5 7\n4 8\n","785\n0\n0\n1972\n144\n0\n0\n0"],["15\n73 83 31 9514 1189 43 79 2 2 1798 5063 2 5 2573 53 \n1 2\n2 3\n1 4\n4 5\n1 6\n3 7\n5 8\n5 9\n6 10\n7 11\n10 12\n9 13\n7 14\n13 15\n","23952214\n633788\n79763\n38056\n4\n0\n13027099\n0\n0\n3596\n0\n0\n0\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}