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

서브태스크 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.

힌트