Author: Aman Kedia
Tester: Sumeet Verma
Editorialist: Sidhant Bansal
Prerequisites - Centroid Decomposition
Difficulty : Medium - Hard
Expected Complexity: O(NlogNd) where d = maximum no. of factors a number has.
You can read about centroid decomposition here - https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree
- Do centroid decomposition of the tree, let this tree be called T and the orignal one be called P.
- Do a dfs on T, and for each node "x", do this -
- Loop through all the nodes(i) in its subtree (of T)
- Now for each gcd_of_path(i, x) update the max and 2nd max_length of all its factors, here gcd_of_path(i, x) returns the gcd of all the edge weights in the path of i to x in the orignal tree (P).
- Example. gcd_of_path(i, x) = 20, then update the max and 2nd_max_length of 1, 5, 10, 20 (ie. all the factors of 20).
- And while updating the max_lengths check if (factor*(max_length_of_factor + 2nd_max_length_of_factor - 1)) is better than the current answer
- Eventually print the answer.
Note - The max_length and 2nd_max_length of gcd path values is calculated independently for each node of T and it is CLEARED every time after we process a node of the T.
Explanation as to why it would work -
When we process a certain node(let it be x) of T, we find out the best path in the subtree of x(in T) such that gcd_of_path(a, b) × len(a, b) is maximum and the path from a to b in the original tree P will pass through x.
The naive method would’ve been to to choose each a and b inside x, and try to maximize gcd_of_path(a, b) x len(a, b).
But this would TLE, so what we do is -
Find all the gcd_of_path(a, x) and len(a, x) for all the nodes in the subtree of x.
Let gcd(gcd(a, x), gcd(b, x)) be ‘m’, then when we update factors of “a” and factors of “b” we would have considered “m” in both the factorization and updated its max and 2nd_max length. So our answer would be m
× (max_length_of_m + 2nd_max_length_of_m - 1). If we assume that “x1, x2, x3, … xk” are the children of node x in T. Then max_length and 2nd_max_length for any “m” shouldn’t be both from the same “xi”. As this case would give us length greater than it actually is.
Complexity analysis - O(NlogNd)
NlogN because a node x in T would affect all its ancestors which can be at max logN, and for the gcd with each ancestor we would factorise it, assuming no. of factors to be at most d for gcd_of_path(a, b). We end up with the complexity of NlogN*d.