First, put the shops on any path of (unweighted) length $$$k$$$. Can you choose a better path?

The optimal path lies completely on the (weighted) diameter.

Try all possible paths in $$$O(n)$$$.

The optimal path lies completely on the (weighted) diameter. Sketch of proof: suppose that the intersection of the chosen path with the diameter is a path $$$u \rightarrow v$$$ ($$$a, u, v, b$$$ in this order). Then, the maximum distance between a node and the nearest shop is one of the following: $$$\text{dist}(a, u)$$$, $$$\text{dist}(v, b)$$$, $$$\text{dist}(c, d)$$$ ($$$d$$$ on the diameter, $$$d$$$ strictly between $$$u$$$ and $$$v$$$, $$$c$$$ in the component of $$$d$$$). Then, $$$u \rightarrow v$$$ itself is optimal.

Now let's try all paths $$$u \rightarrow v$$$ of maximum (unweighted) length (there are $$$O(n)$$$ of them). Notice that the required distance is also the maximum of $$$\text{dist}(a, u)$$$, $$$\text{dist}(v, b)$$$, $$$\text{dist}(c, d)$$$ ($$$d$$$ on the diameter, but not necessarily between $$$u$$$ and $$$v$$$). If you precalculate the distance of each node from the root of its component and from $$$a$$$, $$$b$$$, we can get the maximum distance between a node and the nearest shop in $$$O(1)$$$.

You have to find the maximum total weight of two non-intersecting paths.

Once again, choose any two paths and try to "improve" them.

There are two cases to consider:

• a path is the diameter and the other path lies completely in a component;
• a path is a prefix of the diameter + a vertical path in the corresponding component, the other path is a suffix of the diameter + a vertical path in the corresponding component.

Can you solve them in $$$O(n)$$$?

You have to find the maximum total weight of two non-intersecting paths. Notice that the facts stated previously hold even if weights are on nodes instead of edges.

There are two cases to consider:

• a path is the diameter and the other path lies completely in a component;
• a path is a prefix of the diameter + a vertical path in the corresponding component, the other path is a suffix of the diameter + a vertical path in the corresponding component.

Sketch of proof: suppose that the intersection of a chosen path $$$i \rightarrow j$$$ with the diameter is a path $$$u \rightarrow v$$$ ($$$i$$$ in the component of $$$u$$$; $$$a, u, v, b$$$ in this order). The paths $$$a \rightarrow j$$$, $$$i \rightarrow b$$$, $$$a \rightarrow b$$$ are longer than $$$i \rightarrow j$$$, so it's optimal to take one them instead of $$$i \rightarrow j$$$ if possible.

It's possible to solve both cases in $$$O(n)$$$:

• find the diameter of each component, pick the maximum;
• precalculate the height of each component, the distance of each node from $$$a$$$, $$$b$$$, the prefix maximums $$$\text{pm}(i)$$$ of $$$\text{dist}(a, i) + \text{height}(i)$$$, the suffix maximums $$$\text{sm}(i)$$$ of $$$\text{dist}(i, b) + \text{height}(i)$$$, and find the maximum $$$\text{pm}(i) + \text{sm}(i + 1)$$$.

How to check fast if a path contains an even number of ramen cups?

Let $$$\text{cups}(i, j)$$$ be the parity of the number of cups in the path $$$i \rightarrow j$$$. $$$\text{cups}(i, j)$$$ is the XOR ($$$\oplus$$$) of the number of cups of the edges. $$$\text{cups}(i, j) = \text{cups}(1, i) \oplus \text{cups}(1, j)$$$. You have to find the maximum $$$\text{dist}(i, j)$$$ ($$$\text{cups}(1, i) = \text{cups}(1, j)$$$). Can you reduce the number of candidate longest paths $$$i \rightarrow j$$$?

The optimal path is either $$$a \rightarrow i$$$ or $$$i \rightarrow b$$$. You have to find the maximum $$$\text{dist}(a, i)$$$ among all $$$i$$$ such that $$$\text{cups}(1, i) = \text{cups}(1, a)$$$. What happens when you update an edge?

When you update an edge, you toggle $$$\text{cups}(1, i)$$$ in a subtree. If you order nodes in DFS order, each subtree is represented by a subarray. How to answer queries?

Store $$$-1^{\text{cups}(1, i)} \cdot \text{dist}(a, i)$$$ in a segment tree (same with $$$b$$$, in another segment tree). You have to support range multiply by $$$-1$$$, range max and range min.

Let $$$\text{cups}(i, j)$$$ be the parity of the number of cups in the path $$$i \rightarrow j$$$. $$$\text{cups}(i, j)$$$ is the XOR ($$$\oplus$$$) of the number of cups of the edges. Let $$$l$$$ be $$$\text{lca}(i, j)$$$. Then, $$$\text{cups}(i, j) = \text{cups}(i, l) \oplus \text{cups}(l, j) = \text{cups}(i, l) \oplus \text{cups}(l, 1) \oplus \text{cups}(1, l) \oplus \text{cups}(l, j) = \text{cups}(1, i) \oplus \text{cups}(1, j)$$$.

You have to find the maximum $$$\text{dist}(i, j)$$$ ($$$\text{cups}(1, i) = \text{cups}(1, j)$$$).

Claim: the optimal path is one of the following: $$$a \rightarrow i$$$, $$$i \rightarrow b$$$.

Proof: suppose that $$$i \rightarrow j$$$ is optimal ($$$\text{cups}(1, i) = \text{cups}(1, j)$$$; $$$a$$$, root of $$$i$$$, root of $$$j$$$, $$$b$$$ in this order). $$$a \rightarrow j$$$, $$$i \rightarrow b$$$, $$$a \rightarrow b$$$ are at least as long as $$$i \rightarrow j$$$. If you can't take neither $$$a \rightarrow j$$$ nor $$$i \rightarrow b$$$, you get $$$\text{cups}(1, a) = \text{cups}(1, j) \oplus 1 = \text{cups}(1, i) \oplus 1 = \text{cups}(1, b)$$$, so you can take $$$a \rightarrow b$$$.

After each query, you have to find the maximum $$$\text{dist}(a, i)$$$ among all $$$i$$$ such that $$$\text{cups}(1, i) = \text{cups}(1, a)$$$ (you can handle $$$\text{dist}(i, b)$$$ similarly). For each query, you have to flip all values of $$$\text{cups}(1, i)$$$ in a subtree.

In order to support subtree updates, let's use a segment tree where each leaf represents a node of the tree, and these nodes are in DFS order. Each leaf stores $$$\text{dist}(a, i)$$$ if $$$\text{cups}(1, i) = 0$$$, $$$-\text{dist}(a, i)$$$ otherwise. Flipping a subtree corresponds to multiplying by $$$-1$$$ on a range of the segment tree. Finding the maximum $$$\text{dist}(a, i)$$$ with $$$\text{cups}(1, a) = \text{cups}(1, i)$$$ corresponds to finding either the minimum or the maximum value of the segment tree.