Editorial for COCI '21 Contest 4 #5 Šarenlist

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's look at the set $S$ ~S~ and a family of sets $A_i$ ~A_i~, $i \in \{1, \dots, m\}$ ~i \in \{1, \dots, m\}~:

$S = \{$ ~S = \{~set of all tree colorings $\}$ ~\}~
$A_i = \{$ ~A_i = \{~set of all colorings in which the path between $c_i$ ~c_i~ and $d_i$ ~d_i~ is monochrome $\}$ ~\}~

In terms of these sets, the solution is the size of the set difference between $S$ ~S~ and the union of all the $A_i$ ~A_i~'s. From the inclusion-exclusion formula, we have:

$\displaystyle \left|S \setminus \bigcup_{i=1}^m A_i\right| = \sum_{I \subseteq \{1, \dots, m\}} (-1)^{|I|} \left|\bigcap_{i \in I} A_i\right|$

We use the notation $\bigcap_{i \in \emptyset} A_i = S$ ~\bigcap_{i \in \emptyset} A_i = S~.

Since $m \le 15$ ~m \le 15~, it's possible to iterate over all the $2^m$ ~2^m~ subsets $I \subseteq \{1, \dots, m\}$ ~I \subseteq \{1, \dots, m\}~. For each such subset, we have to determine the size of $\bigcap_{i \in I} A_i$ ~\bigcap_{i \in I} A_i~, i.e. the number of colorings in which each of the paths from $c_i$ ~c_i~ to $d_i$ ~d_i~ is monochrome, for each $i \in I$ ~i \in I~.

The number of such colorings depends on $s$ ~s~, the number of components of the subgraph containing the monochrome paths, and the number of edges $c$ ~c~ which do not belong to any monochrome path. The desired value is then $k^{s+c}$ ~k^{s+c}~. To see this, note that each component (i.e. a set of paths connected by shared edges) can be colored independently into one of $k$ ~k~ colors. Each edge not on one of the paths can also be colored in any of the $k$ ~k~ colors.

The value of $s$ ~s~ can be determined by constructing a graph in which node $i$ ~i~ represents the path between nodes $c_i$ ~c_i~ and $d_i$ ~d_i~, and an edge between $i$ ~i~ and $j$ ~j~ means that the paths between $c_i$ ~c_i~ and $d_i$ ~d_i~ and between $c_j$ ~c_j~ and $d_j$ ~d_j~ have some edge in common. By using a DSU structure or a DFS, we can determine $s$ ~s~ in time complexity $\mathcal O(m^2)$ ~\mathcal O(m^2)~ for each $I$ ~I~.

To calculate the value of $c$ ~c~, we can determine how many edges are in the union of the paths from $c_i$ ~c_i~ to $d_i$ ~d_i~ for $i \in I$ ~i \in I~, and subtract this from the total number of edges, $n-1$ ~n-1~. For each path from $c_i$ ~c_i~ to $d_i$ ~d_i~, we maintain the set of edges it is made up from. Since there are at most $n-1 \le 64$ ~n-1 \le 64~ edges, we can use a bitmask to store these sets, and then a union corresponds to the bitwise or operator $|$ ~|~. Then, with $\mathcal O(mn)$ ~\mathcal O(mn)~ preprocessing, we can determine the value of $c$ ~c~ in $\mathcal O(m)$ ~\mathcal O(m)~.

Adding the complexities of $c$ ~c~ and $s$ ~s~, and multiplying this by the total number of subsets of $I$ ~I~, yields a final time complexity of $\mathcal O(2^m m^2)$ ~\mathcal O(2^m m^2)~. Note that if $n-1 > 64$ ~n-1 > 64~, calculating $c$ ~c~ now takes $\mathcal O(mn \log n)$ ~\mathcal O(mn \log n)~ time, which is too slow. The problem can still be solved for $n \le 10^5$ ~n \le 10^5~, but this is left as an exercise to the reader.

Comments

There are no comments at the moment.