Build a graph over all companies, where two companies are adjacent if they interfere with one another.

What subset of companies can be shut down?

What subset of companies can be left open?

Let ~G~ be the graph over the companies, where ~V(G)~ is the set of companies, and for companies ~i,j \in V(G)~, we have ~ij \in E(G)~ if and only if companies ~i~ and ~j~ interfere. The problem reduces to finding a non-empty set ~U \subseteq V(G)~ where ~G[U]~ is a clique), and ~G[V(G) \backslash U]~ does not contain ~P_3~ (or alternatively, ~G[V(G) \backslash U]~ is a disjoint set of cliques). Intrepid users may immediately observe that graphs that satisfy the previous property resemble split graphs. Indeed, the problem reduces to recognizing if ~G~ is Unipolar.

However, currently the fastest algorithm for recognizing a Unipolar graph runs in ~\mathcal{O}(M^2)~, so naively implementing an algorithm from the internet would blow past the time limit. Moreover, reconstructing ~G~ in any capacity could blow past the time limit, as both ~|E(G)|, |E(G^c)| \in \mathcal{O}(M^2)~, so it'd be impossible to store information on edges.

Lets make some more observations: clearly, if ~G~ contains an induced ~2P_3~ (namely, two fully disjoint copies of ~P_3~), then ~G~ is not Unipolar. This is because no clique can cover both copies of ~P_3~, so no matter what clique is removed, a ~P_3~ will always remain. At a glance, this is not helpful, as checking if a graph is ~2P_3~-free is difficult, does not yield a clique for us to remove, and may not guarantee that ~G~ is Unipolar.

We make an additional observation key to solving the problem, namely that companies ~i~ and ~j~ interfere if and only if the smallest subtree containing every station owned by company ~i~ intersects with the smallest subtree containing every station owned by company ~j~. Thus, ~G~ is the intersection graph of some subtrees. Thus, it turns out that ~2P_3~ is the only obstruction to Unipolarity. We provide a proof: suppose ~G~ does not contain ~2P_3~. For each edge ~e \in E(T)~, let ~S_e \subseteq V(G)~ be the subset of vertices whose subtrees contain ~e~. If ~G-S_e~ does not contain ~P_3~, then ~G~ is Unipolar. Otherwise, let ~T_1,T_2~ be the two trees obtained from deleting ~e~. Since ~G~ does not contain ~2P_3~, then ~G~ only contains one ~P_3~. Moreover, the vertices in said ~P_3~ must correspond to subtrees in the same component (~T_1~ or ~T_2~). Then we direct ~e~ towards the component containing vertices that induce a ~P_3~ in ~G~. Since ~|E(T)|=|V(T)|-1~, there is a vertex ~v~ of ~T~ with no out-going edge. Then removing the clique corresponding to all subtrees that share ~v~ must yield a ~P_3~-free graph.

Our proof also yields an algorithm for checking if a graph is Unipolar. Root ~T~ at its centroid, and let ~T_1,\ldots,T_k~ be components of ~T~ after removing its centroid. We check if removing the clique of ~G~ consisting of all subtrees containing ~T~'s centroid yields a ~P_3~-free graph. If it does, then we conclude. Otherwise, if more than one of ~T_1,\ldots,T_k~ contains subtrees that are a part of a ~P_3~ in ~G~, then we output ~-1~. Otherwise, WLOG suppose that ~T_1~ is the only component containing subtrees that induce a ~P_3~ in ~G~. Then repeat with ~T_1~'s centroid. As the height of the centroid tree is ~\log(N)~, our algorithm runs in ~\mathcal{O}(f(M)\log(N))~ time, where ~f(M)~ is the time it takes to check if ~G~ contains a ~P_3~ after removing a clique. Of course there are some additional subtleties that need to be considered.

There are several algorithms which can yield an optimal value for ~f(M)~, which will be discussed in their respective subtasks

In this case, ~T~ is a path graph, and ~G~ is an interval graph, so removing a vertex from ~T~ yields at most two connected components. We can check there are three intervals that form a ~P_3~ in ~f(M)=\mathcal{O}(M)~ by carefully iterating over the intervals in increasing order of their left endpoint, while maintaining the interval intersecting with the current interval that extends the furthest to the right. Implementation details are left as an exercise.

Time Complexity: ~\mathcal{O}(M\log(N))~

In this case, ~T~ has at most one vertex of degree ~>2~, so it's several paths concatenated at an endpoint. There is no intended algorithm, but a possible solution could be running the algorithm described in Subtask 1 once for each of the graph's branches, then carefully processing each branch to check if there is a ~P_3~ consisting of subtrees that straddle the center vertex.

Time Complexity: ~\mathcal{O}(M\log(N))~ or ~\mathcal{O}((\sum B_i)\log(N))~

What does it mean for a graph to be ~P_3~-free?

Note that a graph is ~P_3~-free if it is a disjoint set of cliques. Consider the following algorithm: first, subdivide ~T~ by adding a vertex on each edge. Next, for a vertex ~v~, let ~C[v]~ denote the number of subtrees that contain ~v~. We say that ~v~ is a local maxima if every path ~v,v_1,v_2,\ldots,v_k~ leading away from ~v~, there is a prefix ~v,v_1,\ldots,v_r~ s.t. ~C[v] \ge C[v_1] \ge \ldots \ge C[v_r]~, and either ~v_r~ is a leaf or ~C[v] > C[v_r]~. We observe that ~G~ is ~P_3~-free if and only if, when walking outwards from any local maxima, ~C[v_i]~ is non-increasing until reaching a vertex ~u~ where ~C[u]=0~. There are multiple ways to construct ~C~. One implementation involves incrementing subtrees offline by "walking inwards" from every leaf of ~T~, while "pushing" vertices owned by companies inwards. Using small-to-large merging yields a runtime of ~f(M) = \mathcal{O}((\sum B_i)\log(\sum B_i)+N)~. Another Implementation involves constructing a virtual tree over the set of stations each company owns, and using Heavy-Light Decomposition to increment subtrees. While this normally takes ~f(M) = \mathcal{O}((\sum B_i)\log^2(N)+N)~, we observe that we don't need to perform incrementations online, so we can use a prefix-sum array to reduce the complexity to ~\mathcal{O}((\sum B_i)\log(N)+N)~. Some additional constant optimizations may be required in both cases.

Time Complexity: ~\mathcal{O}((\sum B_i)\log(\sum B_i)\log(N)+N\log(N))~ or ~\mathcal{O}((\sum B_i)\log^2(N)+N\log(N))~

Thanks to a structural theorem that chordal graphs are precisely the intersection graphs of subtrees, we note that ~2P_3~-free Chordal graphs are precisely the set of Unipolar Chordal graphs. A proof does exist in literature (by A.V. Gagarin), but the paper is not in English, and to the knowledge of the problem author, not available online (so it was not consulted when creating this problem).

Special thanks to Professor Spirkl at the University of Waterloo, who encountered this proof during her research.

To blin00, I hope that the not-so-subtle reference didn't escape you, and that we'll be alright moving forwards.

Addendum: It turns out that blin00 didn't even write the contest. What a weeb...