{"raw_statement":[{"iden":"statement","content":"You are given a tree consisting of $n$ vertices. A number is written on each vertex; the number on vertex $i$ is equal to $a_i$.\n\nLet's denote the function $g(x, y)$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $x$ to vertex $y$ (including these two vertices).\n\nFor every integer from $1$ to $2 \\cdot 10^5$ you have to count the number of pairs $(x, y)$ $(1 \\le x \\le y \\le n)$ such that $g(x, y)$ is equal to this number."},{"iden":"input","content":"The first line contains one integer $n$ — the number of vertices $(1 \\le n \\le 2 \\cdot 10^5)$.\n\nThe second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \\le a_i \\le 2 \\cdot 10^5)$ — the numbers written on vertices.\n\nThen $n - 1$ lines follow, each containing two integers $x$ and $y$ $(1 \\le x, y \\le n, x \\ne y)$ denoting an edge connecting vertex $x$ with vertex $y$. It is guaranteed that these edges form a tree."},{"iden":"output","content":"For every integer $i$ from $1$ to $2 \\cdot 10^5$ do the following: if there is no pair $(x, y)$ such that $x \\le y$ and $g(x, y) = i$, don't output anything. Otherwise output two integers: $i$ and the number of aforementioned pairs. You have to consider the values of $i$ in ascending order.\n\nSee the examples for better understanding."},{"iden":"examples","content":"Input\n\n3\n1 2 3\n1 2\n2 3\n\nOutput\n\n1 4\n2 1\n3 1\n\nInput\n\n6\n1 2 4 8 16 32\n1 6\n6 3\n3 4\n4 2\n6 5\n\nOutput\n\n1 6\n2 5\n4 6\n8 1\n16 2\n32 1\n\nInput\n\n4\n9 16 144 6\n1 3\n2 3\n4 3\n\nOutput\n\n1 1\n2 1\n3 1\n6 2\n9 2\n16 2\n144 1"}],"translated_statement":[{"iden":"statement","content":"给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字，顶点 $i$ 上的数字为 $a_i$。\n\n定义函数 $g(x, y)$ 为从顶点 $x$ 到顶点 $y$ 的简单路径上所有顶点（包括 $x$ 和 $y$）所写数字的最大公约数。\n\n对于从 $1$ 到 $2 \\dot.op 10^5$ 的每个整数，你需要计算满足 $g(x, y)$ 等于该整数的点对 $(x, y)$（其中 $1 \\lt.eq x \\lt.eq y \\lt.eq n$）的数量。\n\n第一行包含一个整数 $n$ —— 顶点的数量 $(1 \\lt.eq n \\lt.eq 2 \\dot.op 10^5)$。\n\n第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ $(1 \\lt.eq a_i \\lt.eq 2 \\dot.op 10^5)$ —— 写在顶点上的数字。\n\n接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \\lt.eq x, y \\lt.eq n, x \\ne y)$，表示连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。\n\n对于从 $1$ 到 $2 \\dot.op 10^5$ 的每个整数 $i$，执行以下操作：如果不存在点对 $(x, y)$ 满足 $x \\lt.eq y$ 且 $g(x, y) = i$，则不输出任何内容；否则输出两个整数：$i$ 和满足条件的点对数量。你必须按 $i$ 的升序输出。\n\n详见示例以更好地理解。"},{"iden":"input","content":"第一行包含一个整数 $n$ —— 顶点的数量 $(1 \\lt.eq n \\lt.eq 2 \\dot.op 10^5)$。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ $(1 \\lt.eq a_i \\lt.eq 2 \\dot.op 10^5)$ —— 写在顶点上的数字。接下来 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \\lt.eq x, y \\lt.eq n, x \\ne y)$，表示连接顶点 $x$ 和顶点 $y$ 的边。保证这些边构成一棵树。"},{"iden":"output","content":"对于从 $1$ 到 $2 \\dot.op 10^5$ 的每个整数 $i$，执行以下操作：如果不存在点对 $(x, y)$ 满足 $x \\lt.eq y$ 且 $g(x, y) = i$，则不输出任何内容；否则输出两个整数：$i$ 和满足条件的点对数量。你必须按 $i$ 的升序输出。详见示例以更好地理解。"},{"iden":"examples","content":"输入31 2 31 22 3输出1 42 13 1输入61 2 4 8 16 321 66 33 44 26 5输出1 62 54 68 116 232 1输入49 16 144 61 32 34 3输出1 12 13 16 29 216 2144 1"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ T = (V, E) $ be a tree with $ |V| = n $, and let $ a: V \\to \\mathbb{Z}^+ $ be a function assigning a positive integer $ a_i $ to each vertex $ i \\in V $.\n\nDefine the function $ g(x, y) = \\gcd\\{ a_v \\mid v \\in \\text{path}(x, y) \\} $, where $ \\text{path}(x, y) $ denotes the set of vertices on the unique simple path between $ x $ and $ y $ in $ T $, including endpoints.\n\nFor each integer $ d \\in [1, 2 \\cdot 10^5] $, let  \n$$\nf(d) = \\left| \\left\\{ (x, y) \\in V \\times V \\mid x \\leq y,\\ g(x, y) = d \\right\\} \\right|.\n$$\n\nCompute $ f(d) $ for all $ d \\in [1, 2 \\cdot 10^5] $, and output each pair $ (d, f(d)) $ such that $ f(d) > 0 $, in increasing order of $ d $.","simple_statement":null,"has_page_source":false}