{"problem":{"name":"E. Surprise me!","description":{"content":"Tired of boring dates, Leha and Noora decided to play a game. Leha found a tree with _n_ vertices numbered from 1 to _n_. We remind you that tree is an undirected graph without cycles. Each vertex _v","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF809E"},"statements":[{"statement_type":"Markdown","content":"Tired of boring dates, Leha and Noora decided to play a game.\n\nLeha found a tree with _n_ vertices numbered from 1 to _n_. We remind you that tree is an undirected graph without cycles. Each vertex _v_ of a tree has a number _a__v_ written on it. Quite by accident it turned out that all values written on vertices are distinct and are natural numbers between 1 and _n_.\n\nThe game goes in the following way. Noora chooses some vertex _u_ of a tree uniformly at random and passes a move to Leha. Leha, in his turn, chooses (also uniformly at random) some vertex _v_ from remaining vertices of a tree (_v_ ≠ _u_). As you could guess there are _n_(_n_ - 1) variants of choosing vertices by players. After that players calculate the value of a function _f_(_u_, _v_) = φ(_a__u_·_a__v_) · _d_(_u_, _v_) of the chosen vertices where φ(_x_) is Euler's totient function and _d_(_x_, _y_) is the shortest distance between vertices _x_ and _y_ in a tree.\n\nSoon the game became boring for Noora, so Leha decided to defuse the situation and calculate expected value of function _f_ over all variants of choosing vertices _u_ and _v_, hoping of at least somehow surprise the girl.\n\nLeha asks for your help in calculating this expected value. Let this value be representable in the form of an irreducible fraction . To further surprise Noora, he wants to name her the value .\n\nHelp Leha!\n\n## Input\n\nThe first line of input contains one integer number _n_ (2 ≤ _n_ ≤ 2·105) — number of vertices in a tree.\n\nThe second line contains _n_ different numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) separated by spaces, denoting the values written on a tree vertices.\n\nEach of the next _n_ - 1 lines contains two integer numbers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_), describing the next edge of a tree. It is guaranteed that this set of edges describes a tree.\n\n## Output\n\nIn a single line print a number equal to _P_·_Q_ - 1 modulo 109 + 7.\n\n[samples]\n\n## Note\n\nEuler's totient function φ(_n_) is the number of such _i_ that 1 ≤ _i_ ≤ _n_,and _gcd_(_i_, _n_) = 1, where _gcd_(_x_, _y_) is the greatest common divisor of numbers _x_ and _y_.\n\nThere are 6 variants of choosing vertices by Leha and Noora in the first testcase:\n\n*   _u_ = 1, _v_ = 2, _f_(1, 2) = φ(_a_1·_a_2)·_d_(1, 2) = φ(1·2)·1 = φ(2) = 1\n*   _u_ = 2, _v_ = 1, _f_(2, 1) = _f_(1, 2) = 1\n*   _u_ = 1, _v_ = 3, _f_(1, 3) = φ(_a_1·_a_3)·_d_(1, 3) = φ(1·3)·2 = 2φ(3) = 4\n*   _u_ = 3, _v_ = 1, _f_(3, 1) = _f_(1, 3) = 4\n*   _u_ = 2, _v_ = 3, _f_(2, 3) = φ(_a_2·_a_3)·_d_(2, 3) = φ(2·3)·1 = φ(6) = 2\n*   _u_ = 3, _v_ = 2, _f_(3, 2) = _f_(2, 3) = 2\n\nExpected value equals to . The value Leha wants to name Noora is 7·3 - 1 = 7·333333336 = 333333338 .\n\nIn the second testcase expected value equals to , so Leha will have to surprise Hoora by number 8·1 - 1 = 8 .","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"厌倦了无聊的约会，Leha 和 Noora 决定玩一个游戏。\n\nLeha 找到一棵包含 #cf_span[n] 个顶点的树，顶点编号从 #cf_span[1] 到 #cf_span[n]。我们提醒你，树是一种无环无向图。树中每个顶点 #cf_span[v] 上写有一个数字 #cf_span[av]。巧合的是，所有写在顶点上的数值互不相同，且是介于 #cf_span[1] 和 #cf_span[n] 之间的自然数。\n\n游戏规则如下：Noora 从树中均匀随机选择一个顶点 #cf_span[u]，并将回合交给 Leha。Leha 在他的回合中，从剩余的顶点中（#cf_span[v ≠ u]）均匀随机选择一个顶点 #cf_span[v]。可以想象，玩家选择顶点的方案共有 #cf_span[n(n - 1)] 种。之后，双方计算所选顶点的函数值 #cf_span[f(u, v) = φ(au·av)] #cf_span[·] #cf_span[d(u, v)]，其中 #cf_span[φ(x)] 是欧拉函数，#cf_span[d(x, y)] 是树中顶点 #cf_span[x] 和 #cf_span[y] 之间的最短距离。\n\n很快，Noora 觉得这个游戏无聊了，于是 Leha 决定缓解气氛，计算函数 #cf_span[f] 在所有选择顶点 #cf_span[u] 和 #cf_span[v] 的方案中的期望值，希望能以某种方式让女孩感到惊喜。\n\nLeha 请求你帮助他计算这个期望值。设该值可表示为最简分数形式 。为更进一步地让 Noora 惊讶，他想告诉她这个值 。\n\n帮助 Leha！\n\n输入的第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 2·105)] —— 树中顶点的数量。\n\n第二行包含 #cf_span[n] 个不同的数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ n)]，用空格分隔，表示写在树顶点上的数值。\n\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]，描述树的一条边。保证这些边构成一棵树。\n\n请在一行中输出一个等于 #cf_span[P·Q - 1] 对 #cf_span[109 + 7] 取模的数。\n\n欧拉函数 #cf_span[φ(n)] 是满足 #cf_span[1 ≤ i ≤ n] 且 #cf_span[gcd(i, n) = 1] 的整数 #cf_span[i] 的个数，其中 #cf_span[gcd(x, y)] 表示 #cf_span[x] 和 #cf_span[y] 的最大公约数。\n\n在第一个测试用例中，Leha 和 Noora 有 #cf_span[6] 种选择顶点的方案：\n\n期望值等于 。Leha 想要告诉 Noora 的值是 #cf_span[7·3 - 1 = 7·333333336 = 333333338] 。\n\n在第二个测试用例中，期望值等于 ，因此 Leha 需要告诉 Hoora 的数字是 #cf_span[8·1 - 1 = 8] 。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 2·105)] —— 树中顶点的数量。\n第二行包含 #cf_span[n] 个不同的数 #cf_span[a1, a2, ..., an] #cf_span[(1 ≤ ai ≤ n)]，用空格分隔，表示写在树顶点上的数值。\n接下来的 #cf_span[n - 1] 行，每行包含两个整数 #cf_span[x] 和 #cf_span[y] #cf_span[(1 ≤ x, y ≤ n)]，描述树的一条边。保证这些边构成一棵树。\n\n## Output\n\n请在一行中输出一个等于 #cf_span[P·Q - 1] 对 #cf_span[109 + 7] 取模的数。\n\n[samples]\n\n## Note\n\n欧拉函数 #cf_span[φ(n)] 是满足 #cf_span[1 ≤ i ≤ n] 且 #cf_span[gcd(i, n) = 1] 的整数 #cf_span[i] 的个数，其中 #cf_span[gcd(x, y)] 表示 #cf_span[x] 和 #cf_span[y] 的最大公约数。\n在第一个测试用例中，Leha 和 Noora 有 #cf_span[6] 种选择顶点的方案：\n#cf_span[u = 1], #cf_span[v = 2], #cf_span[f(1, 2) = φ(a1·a2)·d(1, 2) = φ(1·2)·1 = φ(2) = 1]\n#cf_span[u = 2], #cf_span[v = 1], #cf_span[f(2, 1) = f(1, 2) = 1]\n#cf_span[u = 1], #cf_span[v = 3], #cf_span[f(1, 3) = φ(a1·a3)·d(1, 3) = φ(1·3)·2 = 2φ(3) = 4]\n#cf_span[u = 3], #cf_span[v = 1], #cf_span[f(3, 1) = f(1, 3) = 4]\n#cf_span[u = 2], #cf_span[v = 3], #cf_span[f(2, 3) = φ(a2·a3)·d(2, 3) = φ(2·3)·1 = φ(6) = 2]\n#cf_span[u = 3], #cf_span[v = 2], #cf_span[f(3, 2) = f(2, 3) = 2]\n期望值等于 。Leha 想要告诉 Noora 的值是 #cf_span[7·3 - 1 = 7·333333336 = 333333338] 。\n在第二个测试用例中，期望值等于 ，因此 Leha 需要告诉 Hoora 的数字是 #cf_span[8·1 - 1 = 8] 。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 2 \\cdot 10^5 $, be the number of vertices in a tree.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $, where $ a_i $ is the value on vertex $ i $.  \nLet $ T = (V, E) $ be a tree with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $ of size $ n-1 $.  \nLet $ d(u, v) $ denote the shortest path distance (number of edges) between vertices $ u $ and $ v $ in $ T $.  \nLet $ \\varphi(x) $ denote Euler’s totient function.\n\n**Constraints**  \n1. All $ a_i \\in \\{1, 2, \\dots, n\\} $ are distinct.  \n2. The graph $ T $ is a tree (connected, acyclic, undirected).  \n\n**Objective**  \nCompute the expected value of $ f(u, v) = \\varphi(a_u \\cdot a_v) \\cdot d(u, v) $ over all ordered pairs $ (u, v) $ with $ u \\ne v $:  \n$$\n\\mathbb{E}[f] = \\frac{1}{n(n-1)} \\sum_{\\substack{u,v=1 \\\\ u \\ne v}}^{n} \\varphi(a_u \\cdot a_v) \\cdot d(u, v)\n$$\n\nLet $ \\frac{P}{Q} $ be the irreducible form of $ \\mathbb{E}[f] $.  \nOutput $ P \\cdot Q^{-1} \\mod (10^9 + 7) $, where $ Q^{-1} $ is the modular multiplicative inverse of $ Q $ modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF809E","tags":["divide and conquer","math","number theory","trees"],"sample_group":[["3\n1 2 3\n1 2\n2 3","333333338"],["5\n5 4 3 1 2\n3 5\n1 2\n4 3\n2 5","8"]],"created_at":"2026-03-03 11:00:39"}}