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 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 c \cdot n \cdot log_2(n) \cdot 2^s$$$.

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). Then $$$T(n, s) = n \cdot 2^s + \displaystyle\sum_{i=1}^k T(n_i, s_i)$$$. Prove by induction, so this is not greater than $$$n \cdot 2^s + \displaystyle\sum_{i=1}^k c \cdot n_i \cdot log_2(n_i) \cdot 2^{s_i} \leq n \cdot 2^s + c \cdot 2 \cdot (log_2(n) - 1) \cdot \displaystyle\sum_{i=1}^k n_i \cdot 2^{s_i - 1}$$$. 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 earlier sum is less or equal than $$$n \cdot 2^s + c \cdot 2 \cdot (log_2(n) - 1) \cdot (n + n_i \cdot (2^s - 1)) \leq n \cdot 2^s + c \cdot 2 \cdot (log_2(n) - 1) \cdot (n + \frac{n}{2} \cdot (2^s - 1)) \leq n \cdot 2^s + c \cdot (log_2(n) - 1) \cdot n \cdot (2^s + 1)$$$.