시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 1024 MB135362523.364%

## 문제

You are given an undirected tree with $N$ vertices, labeled with distinct integers from $1$ to $N$.

Let's denote $\textrm {dist}(i,\, j)$ be the length of the shortest path between two vertices $i$ and $j$ on the tree.

Find $\sum_{1 \leq i < j \leq N} \gcd(i,\, j,\, \textrm {dist}(i,\, j))$.
$\gcd(a, b, c)$ means the greatest common divisor of $a$, $b$, and $c$.

## 입력

The first line contains an integer $N$.

Each of the following $N-1$ lines contains two space-separated integers $u_i$ and $v_i$ $(1 \le i \le N-1)$, which means that there is an edge between them.

## 출력

Print the value of $\Sigma_{1 \leq i < j \leq N} \gcd(i,\ j,\ dist(i, j))$.

## 제한

• $3 \leq N \leq 100\,000$
• $1 \leq u_i \leq N$ $(1 \le i \le N-1)$
• $1 \leq v_i \leq N$ $(1 \le i \le N-1)$
• The given graph is a tree

## 서브태스크 1 (10점)

• $N \leq 5\,000$

## 서브태스크 2 (20점)

•     Degree of each vertex is less than 3.

## 예제 입력 1

3
1 2
1 3


## 예제 출력 1

3


## 예제 입력 2

4
1 2
1 3
1 4


## 예제 출력 2

7


## 예제 입력 3

6
1 3
1 5
5 2
6 5
5 4


## 예제 출력 3

20


## 채점 및 기타 정보

• 예제는 채점하지 않는다.