Let $T = (V, E)$ be a undirected tree on $n$ vertices with an arbitrary root. Let the nodes be given weights, by some pre-determined function $W : V(T) \rightarrow \{1, \dots, 10^9\}$. Furthermore, let $S \subseteq V(T)$ be a given set of special nodes in $T$.
Suppose $\mathcal{P}(T) = \{P_1, P_2, \dots, P_k\}$ is a path decomposition of $T$ that satisfies the following:
i) Each path $P_i$ has length at least one.
ii) All paths are pairwise vertex-disjoint, i.e. $i \neq j \implies P_i \cap P_j = \emptyset.$
iii) Each path $P_i$ contains at most one special node and if it contains a special node $s$, then $s$ is an endpoint in $P_i$.
Let $Q_{1}, Q_{2}, \dots, Q_{t} \in \mathcal{P}$ be the paths that include exactly one special node (i.e. discard the paths that have no special nodes). Then for each path $Q_{j}$, suppose $v_1, v_2, \dots, v_q$ (where $v_1 = s$) are the vertices on it. Define: $$\begin{equation}C(Q_{j}) = W(v_q) - \min_{1\leq z\leq q} W(v_z)\end{equation}$$
Finally, define the value ($\Omega$) of such a path decomposition, $\mathcal{P}$ as: $$\begin{equation}\Omega(\mathcal{P}(T)) = \sum_{i=1}^t C(Q_i)\end{equation}$$
Calculate the best possible value over all possible path decompositions of $T$ that adhere to the rules above. Evaluate: $$\displaystyle\max\{\Omega(\mathcal{P}(T))\,|\,\mathcal{P}(T) \text{ is a path decomposition of } T\}$$
Example: Consider the tree $T$ in this image.
The brown vertices are special nodes and each vertex has a weight as well as an id. A specific path decomposition $\mathcal{P}(T)$ is color coded; pink, purple, red and blue. Note that green edges are not included in any of the paths. One can check that this decomposition adheres to the rules discussed above.
Also, we can see that the cost ($C$) of the pink path is $4$, the blue path is $5$, the red path is $2$ and the purple path is $1$, giving a total value of $4 + 5 + 2 + 1 = 12$. One can verify that this is a path decomposition that gives the optimum $\Omega$ value.
Remark: This problem is taken from IEEExtreme 13.0 and is titled Merchant Association. I have taken the liberty to strip the context from the problem and formulate a combinatorial problem out of it. Any insights about this problem are welcome.