Hierarchy

Observation 1

This problem looks like it wants some scary directed-tree algorithm. It doesn't. The qualification constraint completely neuters the hard part.

For every allowed application $u \to v$, we know

$$q_u > q_v.$$

So if $v$ chooses $u$ as its supervisor, then moving upward in the hierarchy strictly increases qualification.

That immediately implies:

• a directed cycle is impossible, because along a cycle we'd need $q_{x_1} < q_{x_2} < \cdots < q_{x_k} < q_{x_1},$ which is nonsense;
• if every employee except one has exactly one supervisor, the result is automatically a rooted tree.

So the usual headache of "what if my parent choices create a cycle?" is gone. Dead. Buried.

Observation 2

Who can be the root?

Any employee with maximum qualification cannot have a supervisor at all, because there is no employee with strictly larger qualification.

Therefore:

• if the maximum qualification appears more than once, then all those employees would have to be roots;
• but the hierarchy must have exactly one root.

So a necessary condition is:

$$\text{there is exactly one employee } r \text{ with maximum } q.$$

And if that holds, $r$ is forced to be the root.

Observation 3

Now fix that unique root $r$.

Every other employee $v \ne r$ must choose exactly one supervisor, i.e. exactly one incoming application $u \to v$.

Since cycles cannot happen, the choices for different vertices are completely independent. There is no global interaction left. For each vertex $v \ne r$, we should simply take the cheapest incoming edge.

So the optimal answer is

$$\text{ans} = \sum_{v \ne r} \min_{(u\to v)} c(u,v).$$

If some employee $v \ne r$ has no incoming application at all, then building the hierarchy is impossible.

Why does this really form one tree?

After choosing one incoming edge for every employee except $r$:

• $r$ has indegree $0$;
• every other node has indegree $1$.

Follow supervisor pointers upward from any node. Qualifications strictly increase, so the chain cannot continue forever and cannot cycle. It must end at a node with no supervisor. But there is only one such node: $r$.

Hence every employee reaches $r$, so all employees belong to the same rooted tree.

Algorithm

1. Find the maximum qualification.
2. If it occurs more than once, print $-1$.
3. Let $r$ be the unique employee with maximum qualification.
4. For every application $a \to b$ with cost $c$, keep $$\text{best}[b] = \min(\text{best}[b], c).$$
5. For every employee $v \ne r$:
   • if $\text{best}[v]$ does not exist, print $-1$;
   • otherwise add it to the answer.

Complexity

We scan the employees once and the applications once.

• Time: $O(n + m)$
• Memory: $O(n)$

Very cheap. Almost suspiciously cheap. But the strict qualification order is doing all the heavy lifting.