MXPATH - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes

Problem Link

Practice

Contest

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.

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

1 Like

Can u explain this line :
"So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components. "?

I am assuming that when we add a vertex u,we are calculating maximum value of dist(u,some v in its connected component).

I couldnt understand why we are calculating diameter.

We want to maximize distance. in a graph the distance between the two farthest nodes is called diameter.

1 Like

Thank you so much!! (My fault,didnt read the question properly

Really sorry if this question feels stupid,but can u explain this line: “So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components”,i mean what if the minimum doesnt lie on the diameter path.

note that we are adding the vertices in descending order. If the minimum is not in the diameter, then we already processed it before.

3 Likes

Its really rare to see editorialists heartily replying to queries. The community appreciates your gesture @alei :slight_smile:

@alei ,got it

Thank you soo much!!