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

문제

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점)

This subtask has an additional constraint: 

  • $N \leq 5\,000$

서브태스크 2 (20점)

This subtask has an additional constraint: 

  •     Degree of each vertex is less than 3.

서브태스크 3 (70점)

This subtask has no additional constraints.

예제 입력 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

출처

University > KAIST > 2022 KAIST RUN Spring Contest F번

채점 및 기타 정보

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