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)$$$.

$$$\operatorname{lcm}(x, x + 1) + \operatorname{lcm}(x + 1, x) = x^2 + (x + 1)^2 - 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 can 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

The quote is just a modification of the original title of KonoSuba.

This is just something I invented, no reference here. Hope you liked the short poem!

The quote is the meme "people die when they are killed" in the Fate series, changed to fit the programming context. And the title is just "Fate Zero" changed to "Sort Zero".

"Do you have a wish?" is a recurring phrase in the LN series HakoMari, referring to the wish granting "boxes". The title is just "Empty Box" changed to "Empty Graph". Also, "O_o" is a reference to one of the main characters, "O".

The quote can probably be traced to many origins, but I personally modified the quote "We are legion, for we are many" from the series 86. There were also a lot of 6's and 8's in the sample, which might have helped you guess.

I didn't really think about this one, just modified a quote from Vivy a bit.