Editorial for DMOPC '21 Contest 1 P4 - Uneven Forest
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
We first consider a binary search on the resulting unevenness. To check whether it is possible to have an unevenness of , let's run a DP on every tree in the forest, rooting each tree arbitrarily. Let
be the minimum cost such that the longest path down from node
has a length of
. Also, we have an array
, which stores the minimum cost to let the subtree rooted at
be valid. For a child
of node
we have two transitions; we can cut the edge
or keep it. Let
and
be the length and beauty of edge
respectively. If we cut the edge, then we simply let
. If we keep it, then we need to merge it with our current DP, so
, taking care that
does not exceed
.
At first, it seems like the complexity of our DP is horrid. After all, the size of the second dimension can be insanely large, and the second transition could square that large number. However, note that each node has at most
different values of
, where
is the number of nodes in the subtree of
. Therefore, the amortized complexity of our algorithm is actually
, using the same proof for the time complexity of tree convolutions!
We can implement the DP using a map for each node, for a total complexity of with a moderate constant factor.
Comments
What is the definition of a "tree convolution"? A Google search only brings up tree-based convolutional neural networks.
Discrete convolution is defined as
.
Based on my understanding, the "tree convolution" in editorial is
, where
is
's parent node. The operation is the similar form of convolution.
bruce is so chad
I found this, haven't entirely read through it myself but it looks pretty comprehensive and defines "tree convolution DP" as "a particular kind of DP solution that occurs on rooted trees. It is a DP solution which naively looks like it runs in
but in fact runs int
." 4fecta also sent me this codeforces blog which you might find useful as well.