Vessels, Heights and Two Versions (Hard Version)

1. Turn the water into a graph metric

Fix the vessel $s$ that must remain empty, so $w_s=0$.

Consider another vessel $v$. Suppose we try to make $w_v=x$. Take any path from $s$ to $v$ whose edge heights are all strictly smaller than $x$. Starting from $v$, across the last edge of that path we have one endpoint with value $x$ and the edge height is below $x$, so the condition forces the previous vessel to also have value $x$. This propagates all the way back to $s$, forcing $w_s=x$, which is impossible.

Therefore every valid array satisfies

$$w_v \le \min_{P:s\to v}\ \max_{e\in P} h_e.$$

Define this minimax/bottleneck distance as

$$d(s,v)=\min_{P:s\to v}\ \max_{e\in P} h_e.$$

Now the nice part: setting

$$w_v=d(s,v)$$

for every vertex $v$ is always good.

For an edge $(u,v)$ of height $h$, the bottleneck distances satisfy

$$d(s,v) \le \max(d(s,u),h),$$

because we can go from $s$ to $u$ optimally and then cross this edge. If $d(s,u)<d(s,v)$, then the inequality forces $d(s,v)\le h$. Symmetrically, whenever the two endpoint values differ, their maximum is at most $h$, exactly what the condition requires.

So for empty vessel $s$, the answer is

$$\sum_{v=1}^n d(s,v),$$

with $d(s,s)=0$.

We reduced the entire problem to: for every vertex, sum bottleneck distances to all other vertices in a weighted cycle.

2. Replace the cycle by a path

In any undirected weighted graph, bottleneck distances are preserved by a minimum spanning tree. More precisely, if $T$ is an MST, then for any $u,v$, the bottleneck distance between them equals the maximum edge weight on the unique $u$-$v$ path in $T$.

Proof sketch: let $M$ be the maximum edge on the $u$-$v$ path in the MST. The tree path gives a path with bottleneck $M$, so $d(u,v)\le M$. If there were a path with all edges $<M$, remove an edge of weight $M$ from the MST path; that creates a cut, and the alternative path crosses this cut with an edge $<M$. Replacing would make a cheaper spanning tree. Contradiction. Classic MST black magic, but legal.

For a cycle, an MST is obtained by deleting any edge with maximum height. Thus we delete one maximum edge and get a weighted path/tree with $n$ vertices and $n-1$ edges.

Now the answer for each vertex is:

$$ans[v]=\sum_{u\ne v} \max_{e\in path(u,v)} h_e.$$

3. DSU over edges increasing by weight

Sort the remaining tree edges increasingly by weight.

When processing an edge of weight $x$ that connects two currently separate components $A$ and $B$, all edges already inside those components have weight at most $x$. Therefore for every pair

$$(a,b)\in A\times B,$$

the maximum edge on their final tree path is exactly $x$.

So this edge contributes:

$$ans[a] \mathrel{+}= x\cdot |B| \quad \text{for every } a\in A,$$ $$ans[b] \mathrel{+}= x\cdot |A| \quad \text{for every } b\in B.$$

The only annoying part is adding the same value to every vertex of a DSU component. Doing it naively is quadratic, and quadratic is where submissions go to die.

4. Lazy component tags

For each DSU root, store:

• $sz[root]$: component size,
• $tag[root]$: lazy value added to every vertex currently in this component,
• a list of vertices in the component,
• $base[v]$: personal correction for vertex $v$.

The real current answer of a vertex $v$ is

$$base[v]+tag[find(v)].$$

To add Delta to a whole component, just do:

$$tag[root]\mathrel{+}=\Delta.$$

When merging component $B$ into component $A$, every vertex $v\in B$ must keep the same real value, but its root tag changes from $tag[B]$ to $tag[A]$. So update:

$$base[v]\mathrel{+}=tag[B]-tag[A].$$

Then move $v$ into $A$'s member list.

Always merge the smaller member list into the larger one. Each vertex moves $O(\log n)$ times, so this part is $O(n\log n)$.

Complexity

For each test case:

• sorting edges: $O(n\log n)$,
• DSU small-to-large moves: $O(n\log n)$,
• memory: $O(n)$ plus member lists.

Over all test cases:

$$O\left(\sum n\log n\right),$$

which easily fits the limits.