Hide

Problem A
Tourists

In Tree City, there are n tourist attractions uniquely labeled 1 to n. The attractions are connected by a set of n1 bidirectional roads in such a way that a tourist can get from any attraction to any other using some path of roads.

You are a member of the Tree City planning committee. After much research into tourism, your committee has discovered a very interesting fact about tourists: they LOVE number theory! A tourist who visits an attraction with label x will then visit another attraction with label y if y>x and y is a multiple of x. Moreover, if the two attractions are not directly connected by a road the tourist will necessarily visit all of the attractions on the path connecting x and y, even if they aren’t multiples of x. The number of attractions visited includes x and y themselves. Call this the length of a path.

Consider this city map:

\includegraphics{tourists.jpg}

Here are all the paths that tourists might take, with the lengths for each:
12=4, 13=3, 14=2, 15=2, 16=3, 17=4,
18=3, 19=3, 110=2, 24=5, 26=6, 28=2,
210=3, 36=3, 39=3, 48=4, 510=3

To take advantage of this phenomenon of tourist behavior, the committee would like to determine the number of attractions on paths from an attraction x to an attraction y such that y>x and y is a multiple of x. You are to compute the sum of the lengths of all such paths. For the example above, this is: 4+3+2+2+3+4+3+3+2+5+6+2+3+3+3+4+3=55.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of an integer n (2n200000) indicating the number of attractions. Each of the following n1 lines will consist of a pair of space-separated integers i and j (1i<jn), denoting that attraction i and attraction j are directly connected by a road. It is guaranteed that the set of attractions is connected.

Output

Output a single integer, which is the sum of the lengths of all paths between two attractions x and y such that y>x and y is a multiple of x.

Sample Input 1 Sample Output 1
10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9
55
Hide

Please log in to submit a solution to this problem

Log in