In an optimal answer, for all $$$1 \le i \le n$$$, $$$\operatorname{lcm}(i, p_i) = i \cdot p_i$$$.

$$$\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$$$.

The operation only decreases numbers.

An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.

Suppose there is an index $$$i$$$ such that $$$a_i > a_{i + 1}$$$. What operations do you need to perform to make $$$a_i \le a_{i + 1}$$$?

$$$\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$$$

diameter $$$\le 2 \cdot \min(a_1 \ldots a_n)$$$

diameter $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$

Binary search on the answer or do a clever greedy.

Count the number of "bad" triplets such that $$$\operatorname{lcm}(i, j, k) < i + j + k$$$.

$$$\operatorname{lcm}(i, j, k) \le 2 \cdot k$$$ in a bad triplet.

A triplet is bad iff $$$\operatorname{lcm}(i, j, k) = k$$$ or ($$$\operatorname{lcm}(i, j, k) = 2 \cdot k$$$ and $$$i + j > k$$$).

$$$\operatorname{lcm}(i, j, k) = x$$$ implies $$$i$$$, $$$j$$$, and $$$k$$$ are all divisors of $$$x$$$.

For every $$$k$$$, iterate over all pairs of divisors of $$$2 \cdot k$$$.

Think of the "bad" triplets as of segments $$$[i; k]$$$ with some weight.

Solve in offline.

Let $$$f_v$$$ be the distance to the closest vertex $$$\in L$$$ to $$$v$$$. You can calculate it for every vertex in $$$O(n)$$$.

The distance in the new graph $$$\operatorname{d'}(u, v)$$$ is equal to $$$\min(\operatorname{d}(u, v), f_u + f_v + x)$$$

Suppose there is a vertex $$$v$$$ with $$$f_v > 0$$$. Then there is always a vertex $$$u$$$ in the subtree of $$$v$$$ such that $$$f_u < f_v$$$ and $$$depth_u$$$ > $$$depth_v$$$.

Think small-to-large merging.

Maintain the largest value of $$$depth_v$$$ over all $$$v$$$ with $$$f_v = i$$$ for all needed $$$i$$$.

In this problem, small-to-large merging works in $$$O(n)$$$.

The diameter is $$$\le n$$$. So you increase it by $$$1$$$ at most $$$n$$$ times.

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem

• Good problem
• Mid problem
• Bad problem