背景

    nodgd在NOI2014中跪烂了,恰好遇到了同样跪烂的lzmhhh123和liukaiwen,他们就开始回馈社会,行走江湖,行侠仗义,救世济民。

描述

    这些天他们村里受旱灾了,他们三人决定给村里一些路口挖井来缓解旱灾。
    他们村的地形可以抽象为一颗树,每个路口是树上一个节点,每条路连接两个路口。所有路口按照修建的先后顺序被编号为1,2,...,N。村里一种奇怪的迷信认为,如果第x个路口与第φ(x)个路口连接,那么会带来各种吉祥,所以村里每个村子都是严格按照这个规则修建的。其中φ是欧拉函数。
    问题是这样产生的:每个路口都需要供水,但如果每个路口都挖井显然是很耗费人力物力的事情,因为每个没有挖井的路口都可以花费一些运费到最近的路口取水,从而可能会减少总的费用。
    经过考察,他们得到了一些数据,包括挖一口井的费用cost0,和一个路口经过k条路后到另一个路口取水的费用costk,他们想知道总的费用最少是多少。

输入格式

    第一行两个数N,cost0,表示总的路口数量和挖一口井的费用。
    第二行N-1个数,第k个数表示一个路口经过k条路后到另一个路口取水的费用costk

输出格式

    输出一个数,表示最小费用。

样例输入1

3 3
1 2 

样例输出1

5

样例输入2

4 1
2 3 4 

样例输出2:

4

样例解释

    样例第一组。村子的形状如图1。在2号路口挖井,1,3号都到2号节点取水,总费用为5。不存在更优的方案。

    样例第二组。村子的形状如图2。在每个路口都挖井显然是最优方案。

数据范围与约定

对于10%的数据,N<=20
对于40%的数据,N<=200
对于60%的数据,N<=2000
对于100%的数据,N<=200000,cost0<=2000,1<=cost1<=cost2<=...<=costN-1<=109

来源

原创