[BOJ 7139] Toll
Task
Let’s define the following notation:
- $\mathcal{G}(V) := \Set{ (V,E) | E \subseteq \dbinom{V}{2} }$
- $\mathcal{G}_C(V) := \Set{ G \in \mathcal{G}(V) | G \text{ is connected} }$
- $\mathcal{F}(V) := \Set{ G \in \mathcal{G}(V) | G \text{ is a forest} }$
- $\mathcal{T}(V) := \mathcal{F}(V) \cap \mathcal{G}_C(V)$
- $\mathcal{ST}(G) := \Set{ (V(G),F) \in \mathcal{T}(V(G)) | F \subseteq E(G) }$
- A path from $u$ to $v$ in a graph $G$ is a vertex-edge sequence $P=(v_0,e_1,v_1,\ldots,e_\ell,v_\ell)$ such that $v_0=u$, $v_\ell=v$, $e_j=\set{v_{j-1},v_j}\in E(G)$, and $v_0,\ldots,v_\ell$ are distinct. We also allow the length-zero path $(u)$.
- $\mathcal{P}_G(u,v)$: the set of all paths from $u$ to $v$ in $G$.
- For a path $P=(v_0,e_1,v_1,\ldots,e_\ell,v_\ell)$, $E(P):=\set{e_1,\ldots,e_\ell}$.
- $u\simeq_G v \iff \mathcal{P}_G(u,v)\neq\emptyset$.
- If $T$ is a tree, $P_T(u,v)$ denotes the unique element of $\mathcal{P}_T(u,v)$.
That is, $\mathcal{T}(V)$ is a set of trees on $V$, and $\mathcal{ST}(G)$ is a set of spanning trees of $G$.
An undirected connected graph $G_0=(V,E_0)\in \mathcal{G}_C(V)$ is given with $V=\set{1,\cdots,N}$ and $\card{E_0}=M$. A new set of edges $E_1 = \Set{ e_1, \cdots, e_K }$ is given so that we are going to make a spanning tree $T\in \mathcal{ST}(G_1)$, where $G_1=(V,E_0\sqcup E_1)$. Every edge $e\in E_0$ has a distinct fixed cost $c_e$, and we should assign a cost $f_i$ to each edge $e_i\in E_1$. Then we can think of a weight function $w_{\b{f}}: E_0\sqcup E_1 \to \mathbb{R}_{>0} $, where $ w_{\b{f}} \big|_{E_0}$ is one-to-one mapping. Let’s define the set of MST(Minimum spanning tree) of $G_1$ with a given cost $\b{f}$.
\[ \mathcal{M}(\b{f}):= \argmin_{T\in \mathcal{ST}(G_1)} \sum_{e\in E(T)} w_{\b{f}}(e) \]
Also, at each vertex $v\in V$, a weight $p_v \in \mathbb{R}_{>0}$ is assigned to it. The goal is to choose a proper $\b{f}$ so that we can maximize the following objective function:
\[ J(\b{f}) = \max_{ T\in \mathcal{M}(\b{f}) } \sum_{v\in V} p_v \sum_{e\in E(P_T(v,1)) \cap E_1 } w_{\b{f}}(e) \]
Solution
First, we can observe that $e\in E(T)$ in a MST $T \in \mathcal{ST}(G_1)$ divides $T$ into two parts: $T-e$ is composed of one tree with the root (vertex $1$) and another tree without the root. Let $D_T(e)$ be the tree without the root, then we can rewrite the objective function as follows:
\[ \begin{align*} J(\b{f}) &= \max_{ T\in \mathcal{M}(\b{f}) } \sum_{e\in E(T)\cap E_1} w_{\b{f}}(e) \sum_{v\in V(D_T(e))} p_v \nl &= \max_{ T\in \mathcal{M}(\b{f}) } \sum_{e\in E(T)\cap E_1} w_{\b{f}}(e) q_T(e) \end{align*} \]
by defining the following quantity:
\[ q_T(e) := \sum_{v\in V(D_T(e))} p_v \]
Now, for a fixed $T \in \mathcal{ST}(G_1)$, let’s define $S_T:=E(T)\cap E_1$. Since $T$ is a tree, $S_T$ forms a forest: $(V,S_T)\in \mathcal{F}(V)$. Next, define the following set:
\[ \mathcal{S}:=\Set{S\subseteq E_1 | (V,S)\in\mathcal{F}(V)} \]
For a fixed $S\in\mathcal{S}$, let $T_S$ be the unique spanning tree obtained by joining all edges in $S$ first and then applying Kruskal’s algorithm to $E_0$. Equivalently,
\[ \Set{T_S} := \argmin_{\substack{ T\in\mathcal{ST}(G_1) \nl S_T = S }} \sum_{e\in E(T)\cap E_0} c_e \]
Indeed, after contracting every edge in $S$, this is an MST problem whose remaining edge weights $c_e$ are pairwise distinct, so its minimizer is unique. If $T\in\mathcal{M}(\b{f})$ and $S_T=S$, then
\[ \begin{align*} \sum_{e\in E(T)} w_{\b{f}}(e) &= \sum_{e_i\in S} f_i + \sum_{e\in E(T)\cap E_0} c_e, \end{align*} \]
where the first term is fixed for a fixed $S$. Therefore,
\[ T\in\mathcal{M}(\b{f}) \ \land\ S_T=S \quad\Longrightarrow\quad T=T_S \]
For $e\in E(T_S)$, let $\delta_{T_S}(e)$ be the cut induced by $T_S-e$:
\[ \delta_{T_S}(e) = \Big\{ g \in E_0\sqcup E_1 \;\Big|\; \card{g \cap V(D_{T_S}(e))}=1 \Big\}. \]
For $e_i\in S$, define
\[ \lambda_S(e_i) = \min_{e\in E_0\cap\delta_{T_S}(e_i)} c_e. \]
If $f_i>\lambda_S(e_i)$, then there exists $e\in E_0\cap\delta_{T_S}(e_i)$ such that $c_e=\lambda_S(e_i)<f_i$. Since
\[ T^\prime=T_S-e_i+e\in\mathcal{ST}(G_1), \]
we have
\[ \sum_{g\in E(T^\prime)} w_{\b{f}}(g) = \sum_{g\in E(T_S)} w_{\b{f}}(g)-f_i+c_e < \sum_{g\in E(T_S)} w_{\b{f}}(g) \]
Thus,
\[ T_S\in\mathcal{M}(\b{f}) \quad\Longrightarrow\quad f_i\leq\lambda_S(e_i) \qquad (e_i\in S) \]
On the other hand, let’s choose $\b{f}$ as
\[ f_i= \begin{cases} \lambda_S(e_i) &; e_i\in S \nl L &; e_i\in E_1\setminus S \end{cases} \]
where $\dps L>\max_{e\in E_0} c_e$. Recall that a spanning tree $T$ is an MST if and only if every $e\in E(T)$ is a minimum-weight edge of the cut induced by $T-e$, i.e.,
\[ T\in\mathcal{M}(\b{f}) \iff \forall e\in E(T),\; \forall g\in\delta_T(e) \; : \; w_{\b{f}}(e)\leq w_{\b{f}}(g) \]
For $e_i\in S$,
\[ w_{\b{f}}(e_i) = \lambda_S(e_i) = \min_{e\in E_0\cap\delta_{T_S}(e_i)} c_e. \]
Also, no other edge of $T_S$ crosses $\delta_{T_S}(e_i)$, so
\[ (S\setminus\Set{e_i})\cap\delta_{T_S}(e_i)=\emptyset \]
Every edge in $E_1\setminus S$ has weight $L>\max_{e\in E_0}c_e\geq \lambda_S(e_i)$. Hence, $e_i$ is a minimum-weight edge of $\delta_{T_S}(e_i)$.
For $e\in E(T_S)\cap E_0$, consider the weight function
\[ w^\prime(g) = \begin{cases} 0 &; g\in S,\nl c_g &; g\in E_0,\nl L &; g\in E_1\setminus S \end{cases} \]
By the definition of $T_S$, Kruskal’s algorithm selects $T_S$ with respect to $w^\prime$, so $T_S$ is a MST under $w^\prime$. Since no other edge of $T_S$ crosses $\delta_{T_S}(e)$,
\[ S\cap\delta_{T_S}(e)=\emptyset \]
and hence
\[ c_e \leq c_g \qquad \left( g\in E_0\cap\delta_{T_S}(e) \right) \]
Therefore, after replacing $w^\prime(e_i)=0$ with $w_{\b{f}}(e_i)=\lambda_S(e_i)$ for every $e_i\in S$, every edge in $T_S$ is still a minimum-weight edge of its induced cut, and thus
\[ T_S\in\mathcal{M}(\b{f}). \]
The same argument works whenever $0<f_i\leq\lambda_S(e_i)$ for every $e_i\in S$, after setting $f_j=L$ for every $e_j\in E_1\setminus S$. Since $q_{T_S}(e_i)>0$, for a fixed $S$ we obtain
\[ \begin{align*} \max_{\substack{\b{f} \nl T_S\in \mathcal{M}(\b{f})} } \sum_{e_i\in S} f_i q_{T_S}(e_i) &= \max_{\substack{ 0<f_i\leq\lambda_S(e_i)\nl e_i\in S} } \sum_{e_i\in S} f_i q_{T_S}(e_i) \nl &= \sum_{e_i\in S} \lambda_S(e_i)q_{T_S}(e_i). \end{align*} \]
Hence,
\[ \begin{align*} \max_{\b{f}} J(\b{f}) &= \max_{\b{f}} \max_{ T\in \mathcal{M}(\b{f}) } \sum_{e_i\in S_T} f_i q_T(e_i) \nl &= \max_{S\in\mathcal{S}} \max_{\substack{\b{f}\nl T_S\in\mathcal{M}(\b{f})}} \sum_{e_i\in S} f_i q_{T_S}(e_i) \nl &= \max_{S\in\mathcal{S}} \sum_{e_i\in S} \lambda_S(e_i)q_{T_S}(e_i) \end{align*} \]
Now, let
\[ \Set{T_0} := \argmin_{T\in\mathcal{ST}(G_0)} \sum_{e\in E(T)} c_e. \]
$T_0$ is unique since all $c_e$ are distinct. For $e\in E_0$, define
\[ E_{<e} := \Set{ g\in E_0 \mid c_g<c_e } \]
Then the Kruskal characterization gives:
\[ E(T_0) = \Big\{ e=\{u,v\}\in E_0 \;\Big|\; u\not\simeq_{(V,E_{<e})} v \Big\} \]
Now define
\[ B := \Big\{ e=\{u,v\}\in E_0 \;\Big|\; u\not\simeq_{(V,E_1\cup E_{<e})} v \Big\} \]
Thus, $B$ is exactly the set of edges selected by Kruskal’s algorithm after joining every edge in $E_1$ beforehand. Since $E_{<e}\subseteq E_1\cup E_{<e}$, we have $B\subseteq E(T_0)$. Moreover, for any $S\subseteq E_1$ with $(V,S)\in\mathcal{F}(V)$, $S\cup E_{<e} \subseteq E_1\cup E_{<e}$, and similarly,
\[ E(T_S) = S \sqcup \Big\{ e=\{u,v\}\in E_0 \;\Big|\; u\not\simeq_{(V,S\cup E_{<e})} v \Big\} \]
Hence, $B\subseteq E(T_S)\cap E_0 \subseteq E(T_0)$.
We’ll contract every connected component of $(V,B)$ into one vertex. For $v\in V$, the connected component containing $v$ is written as:
\[ [v]_G = \Set{ u \in V(G) \mid u\simeq_G v } \]
Then, define the corresponding mapping as:
\[ \pi_G: V \to V/\simeq_G : v \mapsto [v]_G \]
where we’ll denote as $\overline{V}:=V/\simeq_{(V,B)} =\Set{ [v]_{(V,B)} \mid v\in V }$. From now on, write $\pi:=\pi_{(V,B)}$. We extend $\pi$ to subsets of $V$ by
\[ \pi(X):=\Set{\pi(x)\mid x\in X}\qquad(X\subseteq V). \]
In particular, for an edge $e=\set{a,b}$, we write $\pi(e)=\set{\pi(a),\pi(b)}$. For an edge set $F$, we also write $\pi(F):=\Set{\pi(e)\mid e\in F}$ whenever these images are edges. Recall the definition of the graph theoretic rank:
\[ \rank(G) = \max\Big\{ \card{F} \;\Big|\; F \subseteq E(G),\; (V(G),F) \in\mathcal{F}(V(G)) \Big\} = \card{V(G)}-\card{V(G)/ \simeq_G} \]
Let’s denote as $\rank_V(E):= \rank(V,E)$ and $r:= \rank_V(E_1)$. Then we have $r\leq\card{E_1}=K$. Order the edges of $B$ as $b_1,\ldots,b_t$ by increasing cost. Immediately before Kruskal’s algorithm selects $b_j$, the connected components formed by the already selected edges are the same as those of
\[ \left(V,E_1\cup E_{<b_j}\right). \]
Since $b_j\in B$, its endpoints lie in different components, so adjoining $b_j$ increases the rank by exactly one. Consequently,
\[ \rank_V(E_1\cup B)=\rank_V(E_1)+\card{B}. \]
After every edge of $E_0$ has been processed, Kruskal’s algorithm connects the graph because $G_0$ is connected. Hence $(V,E_1\cup B)\in\mathcal{G}_C(V)$. Moreover, $B\subseteq E(T_0)$ implies that $B$ is a forest and therefore $\rank_V(B)=\card{B}$. It follows that
\[ \begin{align*} N-1 &= \rank_V(E_1\cup B) \nl &= \rank_V(E_1)+\card{B} \nl &= r+\rank_V(B) \end{align*} \]
Therefore,
\[ \begin{align*} \card{\overline{V}} &= \card{V}-\rank_V(B) \nl &= N-(N-1-r) = r+1 \nl &\leq K+1. \end{align*} \]
Since $B\subseteq E(T_0)$, define $A:=E(T_0)\setminus B$ then
\[ \begin{align*} \card{A} &= \card{E(T_0)}-\card{B} \nl &= (N-1)-(N-1-r) = r \nl &\leq K \end{align*} \]
Whenever a tree $R$ contains $B$, contraction induces a bijection
\[ E(R)\setminus B\longrightarrow E(R/B), \qquad e\longmapsto\pi(e). \]
Indeed, an edge outside $B$ cannot have both endpoints in the same $B$-component, and two different such edges cannot have the same image; either situation would create a cycle in $R$. Applying this observation to $T_0$, the set
\[ \overline{A}:=\pi(A) \]
forms a tree on $\overline{V}$:
\[ \left( \overline{V},\overline{A} \right) \in \mathcal{T}\left(\overline{V}\right) \]
Together with $B\subseteq E(T_S) \cap E_0 \subseteq E(T_0) = B\sqcup A$, we have
\[ E(T_S)\setminus B \subseteq S\sqcup A. \]
Hence, after contracting $B$, every edge of $T_S$ belongs to $\pi(S)\sqcup\overline A$, regarded as a family of edges retaining their original labels. Edges from $S$ and $A$ may have the same pair of contracted endpoints, so this candidate family should temporarily be regarded as a multigraph. In fact, $\overline T_S$ can be reconstructed by first joining every edge of $\pi(S)$ and then processing the edges of $\overline A$ in increasing order of their original costs. Let $\overline{T}_S$ denote this contracted tree, rooted at $\pi(1)$.
\[ \overline{T}_S = \left( \overline{V}, \pi(E(T_S)\setminus B) \right) \in \mathcal{T}\left(\overline{V}\right) \]
For $v\in\overline{V}\setminus\{\pi(1)\}$, let $\operatorname{par}_{\overline{T}_S}(v)$ be its parent in $\overline{T}_S$ and define
\[ \tau_v:=\Set{v,\operatorname{par}_{\overline{T}_S}(v)}, \quad C_v:=V\left(D_{\overline{T}_S}(\tau_v)\right) \]
and for $X\in\overline{V}$, define
\[ \overline{p}_X:= \sum_{v\in X} p_v \]
For $e_i=\set{x_i,y_i}\in S$, define its contracted image by
\[ \overline e_i:=\pi(e_i)=\set{\pi(x_i),\pi(y_i)}. \]
Let $d_i$ be the endpoint of $\overline e_i$ farther from the root $\pi(1)$ in $\overline T_S$. Then
\[ \overline e_i = \set{d_i,\operatorname{par}_{\overline{T}_S}(d_i)} = \tau_{d_i}. \]
The vertices in $\pi^{-1}(C_{d_i})$ are exactly the vertices in the root-free component of $T_S-e_i$. Therefore,
\[ V(D_{T_S}(e_i))=\pi^{-1}(C_{d_i}) \]
and hence
\[ q_{T_S}(e_i) = \sum_{X\in C_{d_i}}\overline{p}_X. \]
The definition of $\lambda_S(e_i)$ gives
\[ \lambda_S(e_i) = \min_{\substack{ e=\set{a,b}\in E_0 \nl \card{\set{a,b}\cap\pi^{-1}\left(C_{d_i}\right)}=1 }} c_e \]
Let $e_i^\star$ be the unique edge attaining this minimum. By the cut property, $e_i^\star\in E(T_0)$. Every edge in $B$ has both endpoints in one $B$-component, whereas $\pi^{-1}\left(C_{d_i}\right)$ is a union of $B$-components. Thus no edge of $B$ crosses this cut, and hence $e_i^\star\in A$. Consequently,
\[ \lambda_S(e_i) = \min_{\substack{ e=\set{a,b}\in A \nl \card{\set{a,b}\cap\pi^{-1}\left(C_{d_i}\right)}=1 }} c_e \]
For $e=\set{a,b}\in A$, the endpoints $\pi(a)$ and $\pi(b)$ are distinct. Since $\overline T_S$ is a tree,
\[ \begin{align*} \card{\set{a,b}\cap\pi^{-1}(C_{d_i})}=1 &\iff \card{\set{\pi(a),\pi(b)}\cap C_{d_i}}=1 \nl &\iff \overline e_i\in E\left(P_{\overline T_S}(\pi(a),\pi(b))\right) \end{align*} \]
It follows that
\[ \lambda_S(e_i) = \min_{\substack{ e=\set{a,b}\in A \nl \overline e_i\in E\left(P_{\overline T_S}(\pi(a),\pi(b))\right) }} c_e \]
Substituting them into the objective function,
\[ \max_{\b{f}}J(\b{f}) = \max_{S\in\mathcal{S}} \sum_{e_i\in S} \left( \min_{\substack{ e=\{a,b\}\in A \nl \overline e_i\in E\left(P_{\overline T_S}(\pi(a),\pi(b))\right) }} c_e \right) \left( \sum_{X\in C_{d_i}}\overline{p}_X \right) \]
$T_0$, $B$, and $A$ can be obtained by Kruskal’s algorithm in
\[ O(M\log M) \]
time. Since
\[ \card{\overline{V}}=r+1\leq K+1 ,\qquad \card{A}=r\leq K \]
after enumerating every $S\subseteq E_1$, each $\overline{T}_S$ and the corresponding objective value can be evaluated in $O(K^2)$ time by tree traversal and path processing. Therefore, the total time complexity is
\[ O\left(M\log M+2^K K^2\right). \]
