Author: Trung Nguyen
Tester and Editorialist: Alei Reyes
Problem Link
Difficulty
Medium - Hard
PREREQUISITES:
Data Structure and Tree
Problem
Given a tree, with values in its vertices, and distances in its edges. We are asked to find the path that maximizes dist(u, v) · min(u, v) · gcd(u,v). Where dist denotes the distance (sum of distances on edges) between vertices, min and gcd denote the minimum and the greatest common divisor of the values of vertices between u and v.
Explanation
The strategy to solve this problem is similar to CO92TREE. First, we will fix the gcd, then the minimum and then we’ll maximize the distance.
Let’s suppose that we want a path with gcd equal to g. Then we only have to look at vertices that have a value multiple of g. Some of this nodes will be connected. Our goal is to maximize min(u,v) · dis(u,v) for every pair of vertices (u,v) that are in the same connected component.
Let’s add the nodes that are multiple of g one by one in decreasing order of value, this will allow us to know which element is the minimum. When vertex u is added, maybe some of its adjacent vertices have already been added, and we’ll have to merge their respective components (this can be done with a disjoint set union data structure).
So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components. So it only remains to know how does the diameter changes when two trees are merged.
Suppose that we merged trees T1 and T2 by drawing an edge e that joins vertices u in T1 with v in T2. The new diameter can be either the diameter of T1, the diameter of T2, or maybe there is a larger path that goes through e. In the last case, we have to find the farthest node to u that is in T1 and the farthest node to v that is in T2.
Now the problem is given a tree, what is the farthest node to a given vertex u. It turns out that if path x, y is a diameter of the tree, then either x or y will be one of the farthest nodes to u. This is more intuitive if we root the tree on its center.
A node with value x will be added once per divisor of x. So the total complexity O(N * max number of divisors of a[i]). We are ignoring the cost of calculating LCA since it can be done in O(1) after preprocessing a sparse table. Also, the cost of DSU is small in practice.
