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