{"problem":{"name":"C. Ilya And The Tree","description":{"content":"Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF842C"},"statements":[{"statement_type":"Markdown","content":"Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex _i_ is equal to _a__i_.\n\nIlya believes that the beauty of the vertex _x_ is the greatest common divisor of all numbers written on the vertices on the path from the root to _x_, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.\n\n_For each vertex the answer must be considered independently._\n\n_The beauty of the root equals to number written on it._\n\n## Input\n\nFirst line contains one integer number _n_ — the number of vertices in tree (1 ≤ _n_ ≤ 2·105).\n\nNext line contains _n_ integer numbers _a__i_ (1 ≤ _i_ ≤ _n_, 1 ≤ _a__i_ ≤ 2·105).\n\nEach of next _n_ - 1 lines contains two integer numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_, _x_ ≠ _y_), which means that there is an edge (_x_, _y_) in the tree.\n\n## Output\n\nOutput _n_ numbers separated by spaces, where _i_\\-th number equals to maximum possible beauty of vertex _i_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ilya 非常喜欢图，尤其是树。在他最近一次去森林的旅行中，Ilya 找到一棵以顶点 #cf_span[1] 为根的有趣树。树上的每个顶点上都写有一个整数，顶点 #cf_span[i] 上写的数是 #cf_span[ai]。\n\nIlya 认为顶点 #cf_span[x] 的美丽值是从根到 #cf_span[x] 的路径上所有顶点（包括 #cf_span[x] 自身）上所写数字的交错和。此外，Ilya 可以将任意一个顶点的数字改为 #cf_span[0]，或者保持所有顶点不变。现在，对于每个顶点，Ilya 想知道它所能达到的最大可能美丽值。\n\n_每个顶点的答案必须独立考虑。_\n\n_根的美丽值等于其上写的数字。_\n\n第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。\n\n请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] —— 树中顶点的数量（#cf_span[1 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[1 ≤ i ≤ n]，#cf_span[1 ≤ ai ≤ 2·105]）。接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]，#cf_span[x ≠ y]），表示树中存在一条边 #cf_span[(x, y)]。\n\n## Output\n\n请输出 #cf_span[n] 个用空格分隔的数，其中第 #cf_span[i] 个数等于顶点 #cf_span[i] 的最大可能美丽值。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a rooted tree, with root at vertex $ 1 $.  \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the array of integers written on the vertices, where $ a_i $ is the value at vertex $ i $.  \nLet $ T = (V, E) $ be the tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $, rooted at vertex $ 1 $.  \nFor each vertex $ x \\in V $, let $ P(x) $ denote the set of vertices on the unique path from the root $ 1 $ to $ x $, inclusive.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 2 \\cdot 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. The graph is a tree.\n\n**Objective**  \nFor each vertex $ x \\in V $, define the *beauty* of $ x $ as:  \n$$\nb(x) = \\gcd\\left( \\{ a_v \\mid v \\in P(x) \\} \\right)\n$$  \nIlya may choose to set *at most one* vertex $ v \\in V $ to $ 0 $ (or leave all unchanged), and the beauty is then computed over the resulting values (with $ \\gcd(S \\cup \\{0\\}) = \\gcd(S) $ if $ S \\neq \\emptyset $, and $ \\gcd(\\{0\\}) = 0 $).\n\nFor each vertex $ x $, compute the **maximum possible beauty** over all choices of at most one vertex to set to $ 0 $, **considering each vertex independently**.\n\nThat is, for each $ x \\in V $, compute:  \n$$\n\\max_{S \\subseteq P(x),\\, |S| \\leq 1} \\gcd\\left( \\{ a_v \\mid v \\in P(x) \\setminus S \\} \\right)\n$$  \nwhere setting $ a_v = 0 $ for $ v \\in S $ is equivalent to excluding $ a_v $ from the GCD computation.\n\n**Note**: The GCD of an empty set is undefined, but since $ P(x) $ always contains the root, and we may remove at most one vertex, the set $ P(x) \\setminus S $ is never empty.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF842C","tags":["dfs and similar","graphs","math","number theory","trees"],"sample_group":[["2\n6 2\n1 2","6 6"],["3\n6 2 3\n1 2\n1 3","6 6 6"],["1\n10","10"]],"created_at":"2026-03-03 11:00:39"}}