Hello Codeforces!

I was solving this problem, and the model approach involves HLD solution, however I came up with some interesting approach with centroids. In short, I wrote $$$dp_{v, cnt, mask}$$$ where $$$v$$$ is vertex in tree in which centroid subtree I am choosing edges, $$$cnt$$$ is number of edges that was taken to the matching and $$$mask$$$ is mask of vertices which were already taken to some of matching edges, but we only consider those vertexes which have edges to vertices outside of $$$v$$$'s centroid subtree.

So this solution works in $$$O(C \log n)$$$ where $$$C$$$ is number of different $$$dp$$$ states, which is equal to $$$\displaystyle\sum_{v=1}^{n} siz_v \cdot 2^{edges}$$$ where $$$siz_v$$$ is size of $$$v$$$'s centroid subtree, and $$$edges$$$ is number of different edges from tree going outside from $$$v$$$'s centroid subtree.

Here is the proof that number of different states is $$$O(n \log^2 n)$$$. Let me know if you notice any mistakes. Thanks to zwezdinv for helping me with proving this.

Let's consider centroid tree which is built recursively like this: we delete the centroid from the tree, build centroid tree for all remaining components and connect roots of these centroid trees to current centroid. For each vertex $$$v$$$ let's consider value $$$e_v$$$ which equals to number of edges going outside the centroid subtree $$$v$$$ to other vertices. Obviously each edge from original tree is vertical path in centroid tree (because one of edge's endpoints is parent of other one in centroid tree). So each edge $$$(u, v)$$$ from original tree where $$$u$$$ is parent of $$$v$$$ in centroid tree adds $$$1$$$ to values $$$e_w$$$ for all $$$w$$$ on path from $$$u$$$ to $$$v$$$ in centroid tree except of $$$u$$$. For simplicity, let's extend each edge from original tree to any leaf in centroid tree. This will only increase $$$c_w$$$ values for some $$$w$$$, so the bound will still be proven.

Let's calculate $$$T(n, s)$$$ which corresponds to bound of $$$C$$$ value for any centroid subtree with exactly $$$n$$$ vertices if $$$c_{root} = s$$$ where $$$root$$$ is the root of this centroid subtree (e.g. $$$s$$$ is number of edges that are going from parents of $$$root$$$ in centroid tree). Want to prove, that $$$T(n, s) \leq n \cdot log_2(n) \cdot 2^s + n \cdot log_2(n)^2$$$.

Suppose $$$n_1, n_2, n_3, \dots n_k$$$ are sizes of children subtrees and $$$s_1, s_2, s_3, \dots s_k$$$ are $$$c_w$$$ for these subtrees roots. We know that $$$\displaystyle\sum_{i=1}^k n_i = n - 1$$$, $$$n_i \leq \frac{n}{2}$$$ and $$$\displaystyle\sum_{i=1}^k (s_i - 1) = s$$$ (because each edge from $$$s$$$ upper edges is going exactly to one of subtrees and one edge from $$$root$$$ appears). Prove by induction, then $$$T(n, s) = n \cdot 2^s + \displaystyle\sum_{i=1}^k T(n_i, s_i) \leq n \cdot 2^s + \displaystyle\sum_{i=1}^k (n_i \cdot log_2(n_i) \cdot 2^{s_i} + n_i \cdot log_2(n_i)^2) \leq$$$

$$$\leq n \cdot 2^s + 2 \cdot (log_2(n) - 1) \displaystyle\sum_{i=1}^k n_i \cdot 2^{s_i - 1} + (log_2(n) - 1)^2 \cdot \displaystyle\sum_{i=1}^k n_i$$$

We know that $$$\displaystyle\sum_{i=1}^k n_i \cdot 2^{s_i - 1}$$$ with $$$\displaystyle\sum_{i=1}^k (s_i - 1) = s$$$ is maximal when one $$$s_i - 1 = s$$$, where $$$n_i$$$ is maximal and other $$$s_i - 1 = 0$$$, so above sum is not greater than

$$$n \cdot 2^s + 2 \cdot (log_2(n) - 1) \cdot (n + \frac{n}{2} \cdot (2^s - 1)) + (log_2(n) - 1)^2 \cdot n \leq$$$

$$$\leq n \cdot 2^s \cdot log_2(n) + n \cdot log_2(n)^2 - n \cdot log_2(n) \leq$$$

$$$\leq n \cdot 2^s \cdot log_2(n) + n \cdot log_2(n)^2$$$

So the bound is proven.

$$$C$$$ equals to $$$T(n, 0) \leq \cdot n \cdot log_2(n)^2 + n \cdot log_2(n) = O(n \cdot log_2(n)^2)$$$.

Also there is a lower bound of $$$\Omega(n \cdot \log_2(n)^2)$$$.

Let's build centroid tree that is full binary tree. Divide this tree into paths to leaf and add to the actual tree the direct edge from every vertex in path to end of this path. Also we direct one more edge from every vertex to subtree that is not on path that this vertex lies in. We can see this is valid centroid tree by proving it inductively. If both subtrees of root are valid centroid trees and root is connected to both of them and divides them into components of size less than half of size of all tree, so root is centroid and transition is proved.

$$$S(k)$$$ denotes $$$C$$$ for such full binary tree of depth $$$k$$$. Consider path that is going from root. This path impacts to $$$C$$$ not less than $$$\displaystyle\sum_{i=0}^k 2^i \cdot 2^{k - i} = 2^k \cdot (k + 1)$$$. If we delete these path, there will be components of depth $$$0, 1, \dots k-1$$$, so $$$S(k) \geq 2^k \cdot (k + 1) + \displaystyle\sum_{i=0}^{k-1} S(i) = \displaystyle\sum_{i=0}^k 2^i \cdot (i + 1) \cdot 2^{k - i} = \frac{2^k \cdot (k + 1) \cdot (k + 2)}{2} = \Omega(n \cdot log_2(n)^2)$$$, so bound is proven and $$$C$$$ is $$$\Theta(n \cdot log_2(n)^2)$$$.

Here is my code for the problem above from 300iq contest.

Also this technique can be used to solve this problem from APIO.