First, break the graph into maximal biconnected components. You can do this by using Tarjan's articulation point algorithm. These are the only companies that you should consider investing into.

For each pair of connected companies, create an edge between them. However, this will create up to ~\binom N 2~ edges, which is too slow to pass. To solve this, we turn the graph into a hypergraph. For each planet, connect all the companies that share it with a virtual edge.

Once we have done this, the graph will be like a tree, but with hyperedges. When starting from a component, scan through all its planets to find the descendent "subtrees". Be very careful to not traverse back up a tree, or sideways as that can lead to an incorrect answer.

For each component, have a dp state of ~[\text{used current?}][\text{investments used}]~. When you find a planet with a "subtree", there are 3 possible conditions for the dp state:

1. You use the current component, and are free to choose any of the descendent components. However, if you use any component directly descendant from the current, you must subtract the profit of the shared planet to avoid double counting.
2. You don't use the current component, and don't use any directly descendent components. This is the standard knapsack tree dp problem.
3. You don't use the current component, and must use at least ~1~ directly descendent component. To solve this, you must create ~2~ inplace dp states and perform knapsack on it.

When you are done, you should have the solution for using all ~K~ investments stored in ~\max(dp[1][0][K], dp[1][1][K])~.

To account for "holding on to investments", simply get the value of:

$$\displaystyle \max_{x=0}^K \left(\max((K-x) \times I + \max(dp[1][0][x]),dp[1][1][x])\right)$$

Time Complexity: ~\mathcal O(NK^2)~