Editorial for DMOPC '21 Contest 1 P4 - Uneven Forest

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.

Author: 4fecta

We first consider a binary search on the resulting unevenness. To check whether it is possible to have an unevenness of $L$ ~L~, let's run a DP on every tree in the forest, rooting each tree arbitrarily. Let $dp_{i, j}$ ~dp_{i, j}~ be the minimum cost such that the longest path down from node $i$ ~i~ has a length of $j$ ~j~. Also, we have an array $good$ ~good~, which stores the minimum cost to let the subtree rooted at $i$ ~i~ be valid. For a child $v$ ~v~ of node $u$ ~u~ we have two transitions; we can cut the edge $(u, v)$ ~(u, v)~ or keep it. Let $len_{u, v}$ ~len_{u, v}~ and $cost_{u, v}$ ~cost_{u, v}~ be the length and beauty of edge $(u, v)$ ~(u, v)~ respectively. If we cut the edge, then we simply let $dp_{u, j} = dp_{u, j} + cost_{u, v} + good_v$ . If we keep it, then we need to merge it with our current DP, so $dp_{u, \max(i, j + len_{u, v})} = dp_{u, i} + dp_{v, j}$ , taking care that $i + j + len_{u, v}$ ~i + j + len_{u, v}~ does not exceed $L$ ~L~.

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 $u$ ~u~ has at most $sz_u$ ~sz_u~ different values of $j$ ~j~, where $sz_u$ ~sz_u~ is the number of nodes in the subtree of $u$ ~u~. Therefore, the amortized complexity of our algorithm is actually $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~, 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 $\mathcal{O}(N^2 \log 10^{12})$ ~\mathcal{O}(N^2 \log 10^{12})~ with a moderate constant factor.

Comments

3

Andycipation commented on Sept. 11, 2021, 2:26 p.m.

What is the definition of a "tree convolution"? A Google search only brings up tree-based convolutional neural networks.

16

bruce commented on Sept. 11, 2021, 3:27 p.m. ← edited →

Discrete convolution is defined as $(f * g)[n] = \sum f[n-m] \times g[m]$ ~(f * g)[n] = \sum f[n-m] \times g[m]~.

Based on my understanding, the "tree convolution" in editorial is $dp[u][i] = \sum dp[u][i-j] \times dp[v][j]$ , where $u$ ~u~ is $v$ ~v~'s parent node. The operation is the similar form of convolution.

5

dxke02 commented on Sept. 11, 2021, 3:39 p.m.

bruce is so chad

3

Nils_Emmenegger commented on Sept. 11, 2021, 3:15 p.m.

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 $\mathcal{O}(N^3)$ ~\mathcal{O}(N^3)~ but in fact runs int $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~." 4fecta also sent me this codeforces blog which you might find useful as well.