GCD on a tree - Editorial

general
, , ,
1

PROBLEM LINK:

Practice

Contest

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.

Editorial -

You can read about centroid decomposition here - https://threads-iiith.quora.com/Centroid-Decomposition-of-a-Tree

  1. Do centroid decomposition of the tree, let this tree be called T and the orignal one be called P.
  2. 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.

1 Like
2

Can do without Centroid Decomposition.

3 Likes
3

Yes, we can do it without using centroid decomposition. Do simple recursive DP on the tree (rooted at node 1). For each node, dp state is :-

  • for a node u we keep maximum length path from node u to any node, say v, in the subtree rooted at u such that GCD(u, v) is divisible by d, for all d which divides the number associated with the edge u to its parent.
  • See https://www.codechef.com/viewsolution/8830864
  • Complexity is also better, i.e., O(N * D), where D is maximum number of factors of any number from 1 to 100000.
  • However, I need to implement the dfs using stacks, because of stack limit error.
3 Likes
4

@karanaggarwal it would be great if you explain your approach in short.

5

For g as gcd, form the forest formed by only those edges whose cost is a multiple of g. And find the diameter of the forest (max diameter of the trees in the forest). Do this for all g. Complexity (summation of number of divisors of each weight)

2 Likes
6

I got accepted using normal recursive DFS.