Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.

But main problem is N (Number of nodes in tree is 100000) So is their any better solution than O(N^2) as I currently have O(N^2) approach to do this problem using LCA between 2 nodes of tree.

So given a tree with N nodes and N-1 edges can we have a better algorithm ?

• Consider a star with $n-1$ nodes linked to the root. Then you have to count the number of coprime pairs in a set of size $n-1$, and do you know any algorithm faster than $O(n^2)$? Also, for a chain I've got an $O(n\log n)$ solution. Mar 10, 2015 at 13:42
• @WillardZhan Ae you asking for algorithm faster than O(n^2) ? I think question itself asks the same thing Mar 10, 2015 at 17:03

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$.

• Can you add some pseudo code or example for better understanding and also complexity of your algorithm ? Mar 11, 2015 at 3:44
The text passage describes a problem in graph theory, specifically about finding pairs of nodes in a tree where the greatest common divisor (gcd) of the labels on the path between the nodes is 1. It also includes a discussion on the complexity of the problem and a proposed algorithm to solve it more efficiently.
single_question_with_answer

1. the passage contains a mathematical question: "we need to calculate the number of unordered pairs (s, t) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between s and t is equal to one."
2. an answer to this question is provided in the form of a proposed algorithm that works by making the tree rooted and working bottom-up, storing the number of successor nodes for each possible gcd value, and then moving this information upwards to compute the number of valid paths.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.

But main problem is N (Number of nodes in tree is 100000) So is their any better solution than O(N^2) as I currently have O(N^2) approach to do this problem using LCA between 2 nodes of tree.

So given a tree with N nodes and N-1 edges can we have a better algorithm ?

• Consider a star with $n-1$ nodes linked to the root. Then you have to count the number of coprime pairs in a set of size $n-1$, and do you know any algorithm faster than $O(n^2)$? Also, for a chain I've got an $O(n\log n)$ solution. Mar 10, 2015 at 13:42
• @WillardZhan Ae you asking for algorithm faster than O(n^2) ? I think question itself asks the same thing Mar 10, 2015 at 17:03

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$.

• Can you add some pseudo code or example for better understanding and also complexity of your algorithm ? Mar 11, 2015 at 3:44
user
The text passage describes a problem in graph theory, specifically about finding pairs of nodes in a tree where the greatest common divisor (gcd) of the labels on the path between the nodes is 1. It also includes a discussion on the complexity of the problem and a proposed algorithm to solve it more efficiently.

TYPE: SINGLE_QUESTION_WITH_ANSWER

1. The passage contains a mathematical question: "We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one."
2. An answer to this question is provided in the form of a proposed algorithm that works by making the tree rooted and working bottom-up, storing the number of successor nodes for each possible gcd value, and then moving this information upwards to compute the number of valid paths.