CF809E Surprise me!

    • 85通过
    • 215提交
  • 题目来源 CodeForces 809E
  • 评测方式 RemoteJudge
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 8000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定一棵 $n$ 个节点的树,每个点有一个权值 $a[i]$ ,保证 $a[i]$ 是一个 $1..n$ 的排列。 求 $$\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i*a_j)·dist(i,j)$$ 其中, $\varphi(x)$ 是欧拉函数, $dist(i,j)$ 表示 $i,j$ 两个节点在树上的距离。

    感谢@yybyyb 提供的翻译

    题目描述

    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 $ 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 $ .

    The 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.

    Soon 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.

    Leha 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 .

    Help Leha!

    输入输出格式

    输入格式:

    The first line of input contains one integer number $ n $ $ (2<=n<=2·10^{5}) $ — number of vertices in a tree.

    The 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.

    Each 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.

    输出格式:

    In a single line print a number equal to $ P·Q^{-1} $ modulo $ 10^{9}+7 $ .

    输入输出样例

    输入样例#1: 复制
    3
    1 2 3
    1 2
    2 3
    
    输出样例#1: 复制
    333333338
    
    输入样例#2: 复制
    5
    5 4 3 1 2
    3 5
    1 2
    4 3
    2 5
    
    输出样例#2: 复制
    8
    

    说明

    Euler'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 $ .

    There are $ 6 $ variants of choosing vertices by Leha and Noora in the first testcase:

    • $ u=1 $ , $ v=2 $ , $ f(1,2)=φ(a_{1}·a_{2})·d(1,2)=φ(1·2)·1=φ(2)=1 $
    • $ u=2 $ , $ v=1 $ , $ f(2,1)=f(1,2)=1 $
    • $ u=1 $ , $ v=3 $ , $ f(1,3)=φ(a_{1}·a_{3})·d(1,3)=φ(1·3)·2=2φ(3)=4 $
    • $ u=3 $ , $ v=1 $ , $ f(3,1)=f(1,3)=4 $
    • $ u=2 $ , $ v=3 $ , $ f(2,3)=φ(a_{2}·a_{3})·d(2,3)=φ(2·3)·1=φ(6)=2 $
    • $ u=3 $ , $ v=2 $ , $ f(3,2)=f(2,3)=2 $

    Expected value equals to . The value Leha wants to name Noora is $ 7·3^{-1}=7·333333336=333333338 $ .

    In the second testcase expected value equals to , so Leha will have to surprise Hoora by number $ 8·1^{-1}=8 $ .

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。