25119번 - Tree GCD 서브태스크다국어

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

This subtask has an additional constraint: 

• $N \leq 5\,000$

This subtask has an additional constraint: 

•     Degree of each vertex is less than 3.

This subtask has no additional constraints.