{"raw_statement":[{"iden":"statement","content":"你有一棵以 1 为根的树，统计点对 $(x, y)$，满足 $a_{lca(x,y)}$ 是 $a_x$ 和 $a_y$ 的公约数。注意当\n$x \\neq y$ 时 $(x, y)$ 和 $(y, x)$ 视为不同的点对。\n\n"},{"iden":"input","content":"第一行一个整数 $n$。\n\n第二行 $n$ 个整数 $a_i$。\n\n第三到 $n + 1$ 行，每行两个整数，表示树上的边。"},{"iden":"output","content":"一行一个整数表示答案。"},{"iden":"note","content":"### 样例解释\n\n以下点对满足条件：$(1, 1)$，$(1, 3)$，$(1, 5)$，$(2, 2)$，$(3, 1)$，$(3, 3)$，$(3, 5)$，$(4, 4)$，$(5, 1)$，$(5, 3)$，$(5, 5)$。\n\n### 数据范围\n\n本题数据分为多个子任务，具体如下：\n\n| 子任务编号 | $n$ | 附加条件 | 子任务分数 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $\\leq 150$ | 无 | $10$ |\n| $2$ | $\\leq 1500$ | 无 | $10$ |\n| $3$ | $\\leq 10^5$ | 树为随机生成 | $10$ |\n| $4$ | $=99998$ | $a_i\\leq 300$ | $10$ |\n| $5$ | $=99998$ | $a$ 为 $1\\sim n$ 的排列 | $10$ |\n| $6$ | $\\leq 10^5$ | 无 | $50$ |\n\n\n对于所有数据，保证 $1 \\leq a_i \\leq n$。"}],"translated_statement":null,"sample_group":[["5\n2 3 2 5 4\n1 2\n1 3\n2 4\n2 5","11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}