Edit: This problem came to our national level informatics competition and I can't find the original source or an online judge for it

Say we have two functions $$$g(u, v)$$$ and $$$d(u, v)$$$ for a tree with $$$N$$$ nodes and $$$N - 1$$$ edges. The edges are bidirectional.

• $$$g(u, v)$$$ — GCD of weights on edges from node $$$u$$$ to $$$v$$$.
• $$$d(u, v)$$$ — Number of edges we have to traverse through to get from node $$$u$$$ to $$$v$$$. Since it's a tree, only one path exists.

Note that $$$d(u, v)$$$ doesn't return the sum of weights on path from $$$u$$$ to $$$v$$$.

So now, for each possible node $$$v$$$ for node $$$u$$$ ($$$u \neq v$$$) where $$$g(u, v) \gt 1$$$ find node $$$v$$$ such that $$$d(u, v)$$$ is maximized. If there is no $$$v$$$ that satisfies the said conditions, return $$$0$$$.

For example, consider the following graph:

11
1 2 6
1 3 9
2 4 1
2 5 6
3 6 3
3 7 5
4 8 2
4 9 4
5 10 8
5 11 1

Result for each node would be: 3 3 3 1 4 4 1 2 2 3 0

For node $$$1$$$:

• $$$g(1, 10) = gcd(6, 6, 8) = 2 \gt 1$$$.

• $$$d(1, 10) = 3$$$ so we must return $$$3$$$.

For node $$$5$$$:

• $$$g(5, 6) = gcd(6, 6, 9, 3) = 3 \gt 1$$$.

• $$$d(5, 6) = 4$$$ so we must return $$$4$$$.

For node $$$11$$$:

• The only edge going out from node $$$11$$$ is an edge with weight of $$$1$$$ and since $$$gcd(1, N) = 1$$$, we must return $$$0$$$.

$$$N^{2}$$$ solution can be easily found where $$$N$$$ is the number of nodes in the tree. However I know that solution faster than $$$N^{2}$$$ exists and I can't grasp it. Any help would be appreciated.