UPD: The full version is here.

1. Strong Password

It's obvious that the best insertion method is to find two same adjacent characters and add a difference to it, and that increases the time by $$$3$$$.

If there isn't a pair like that, we can simply add a character different to the back of the string, to increase the time by $$$2$$$.

2. Make Three Regions

Since there is at most $$$1$$$ connected component in the input graph, and there are only $$$2$$$ rows, so a legal construction only acts like this:

.0.
x.x

or you can flip it by the x-axis.

3. Even Positions

Define $$$n$$$ is size of $$$s$$$, $$$s'$$$ is $$$s$$$ after restoration, and

Then, for all integers $$$i$$$ in range $$$[1,n]$$$, $$$p_i$$$ shouldn't less than $$$r_i$$$.

So, just greedily construct $$$s'$$$ by checking each $$$r_i$$$ in time.

4. Maximize the root

The overall strategy is able to be called "maximize the minimum". Apply depth-first search on the tree, and when you finish all "maximize the minimum" for vertex $$$x$$$'s childs, if $$$a_x$$$ is lower than all $$$a_i$$$ where $$$i$$$ is in $$$x$$$'s subtree and $$$x\neq i$$$, then set $$$a_x$$$ to the floor average of $$$a_x$$$ and $$$\min(a_i)$$$. Otherwise, don't perform operations.

Answer is $$$a_1+\min_{i=2}^n a_i$$$.

5. Level Up

Observed that for each $$$i$$$, there exists a constant $$$c_i$$$ that $$$i$$$-th monster always fight with Monocarp when $$$k\ge c_i$$$.

Apply binary search with a BIT to find $$$c_i$$$, which has a time complexity of $$$O(n\log^2 (2\times 10^5))$$$, then we can answer each query in constant time.