Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1
If there are a lot of large numbers on the edges I do not know, but if the number of different prime factors on the edges is limited there seems to be an efficient algorithm.

The approach is as in Longest path in an undirected tree with only one traversal.

Make the tree rooted, so you can work bottom up. In each node $v$ keep for each possible number $d$ the number of successor nodes in the tree that have a path up to $v$ with gcd $d$. If we move up in the tree we extend the paths of the children (taking into account the values on the edges) to the parent, and count the paths that connect two successors that run via the parent (if the ggd's are $1$).

Each node is visited only once, but there is quite some work between edges at each node.

Example.



At node $g$ we store $1$ incoming path with gcd $3\cdot 5$, and  $1$ incoming path with gcd $3\cdot 7$: $[3\cdot 5\to 1, 3\cdot 7 \to 1]$.
At node $h$ we store: $[5\to 1, 5^2\to 1, 7 \to 1]$.
At node $i$ we store: $[3\cdot 7\to 1, 5\to 1, 5\cdot 7 \to 1]$.

With this information we obtain zero paths via $g$ with gcd $1$, two paths via $h$ with gcd $1$, and one path via $i$ with gcd $1$.

We now move the path info upwards. One new path from $g$ to $j$ with gcd $3^2\cdot 7$, and we add the info from $g$ after performing the gcd with the last edge:  $[3\to 1, 3\cdot 7 \to 1, 3^2\cdot 7\to 1]$.
One new path from $h$ to $j$ with gcd $2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[5\to 2, 1 \to 1, 2\cdot 5\to 1]$.
One new path from $i$ to $j$ with gcd $3^2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[3\to 1, 5 \to 2, 3^2\cdot 5\to 1]$.

Altogether we store at $j$:  $[3\to 2, 3\cdot 7 \to 1, 3^2\cdot 7\to 1,5\to 4, 1 \to 1, 2\cdot 5\to 1, 3^2\cdot 5\to 1$. This info is bounded by the possible divisors of the edge labels.

We finally compute the `via' count at $j$ by considering the lists at pairs of children. Quite some work. All paths from $g$ and from $h$ have gcd $1$, so we count $3\cdot 4 = 12$. I count $6$ between $h$ and $i$, and $3$ between $g$ and $i$.