Editorial for COCI '21 Contest 4 #5 Šarenlist
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's look at the set and a family of sets
,
:
set of all tree colorings
set of all colorings in which the path between
and
is monochrome
In terms of these sets, the solution is the size of the set difference between and the union of all the
's. From the inclusion-exclusion formula, we have:
We use the notation .
Since , it's possible to iterate over all the
subsets
. For each such subset, we have to determine the size of
, i.e. the number of colorings in which each of the paths from
to
is monochrome, for each
.
The number of such colorings depends on , the number of components of the subgraph containing the monochrome paths, and the number of edges
which do not belong to any monochrome path. The desired value is then
. To see this, note that each component (i.e. a set of paths connected by shared edges) can be colored independently into one of
colors. Each edge not on one of the paths can also be colored in any of the
colors.
The value of can be determined by constructing a graph in which node
represents the path between nodes
and
, and an edge between
and
means that the paths between
and
and between
and
have some edge in common. By using a DSU structure or a DFS, we can determine
in time complexity
for each
.
To calculate the value of , we can determine how many edges are in the union of the paths from
to
for
, and subtract this from the total number of edges,
. For each path from
to
, we maintain the set of edges it is made up from. Since there are at most
edges, we can use a bitmask to store these sets, and then a union corresponds to the bitwise or operator
. Then, with
preprocessing, we can determine the value of
in
.
Adding the complexities of and
, and multiplying this by the total number of subsets of
, yields a final time complexity of
. Note that if
, calculating
now takes
time, which is too slow. The problem can still be solved for
, but this is left as an exercise to the reader.
Comments