题目描述

In Tree City, there are $n$ tourist attractions uniquely labeled $1$ to $n$. The attractions are connected by a set of $n - 1$ 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:

:::align{center} :::

Here are all the paths that tourists might take, with the lengths for each:
$1 \to 2 = 4$, $1 \to 3 = 3$, $1 \to 4 = 2$, $1 \to 5 = 2$, $1 \to 6 = 3$, $1 \to 7 = 4$,
$1 \to 8 = 3$, $1 \to 9 = 3$, $1 \to 10 = 2$, $2 \to 4 = 5$, $2 \to 6 = 6$, $2 \to 8 = 2$,
$2 \to 10 = 3$, $3 \to 6 = 3$, $3 \to 9 = 3$, $4 \to 8 = 4$, $5 \to 10 = 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$.

输入格式

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$ ($2 \leq n \leq 200,000$) indicating the number of attractions. Each of the following $n - 1$ lines will consist of a pair of space-separated integers $i$ and $j$ ($1 \leq i < j \leq n$), denoting that attraction $i$ and attraction $j$ are directly connected by a road. It is guaranteed that the set of attractions is connected.

输出格式

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

10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9

55