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 $$$c_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 $$$c_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 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.

UPD: There is a way to reduce the runtime to $$$O(n \cdot log_2(n))$$$. Thanks to dooglius for providing this beautiful solution! Here is how it works:

Let's build our "pseudo-centroid" tree recursively. On each iteration we have some set of vertices which will correspond to some centroid subtree in our final construction. Also, some of these vertexes from the set already have edges from original tree going outside of this set. We want to keep number of such vertex $$$\leq 2$$$ at every moment. Obviously, at each stage we want for these vertexes to form a connected subgraph of the initial tree.

If there are $$$\leq 1$$$ vertexes with edges going outside of current set, let's pick the centroid of our set in the initial tree and run recursively from each of its subtrees from the set. After this operation, each of centroid's subtrees would have $$$\leq 2$$$ edges going outside of the subtree (one edge is added from the centroid), so our condition is still kept.

The tricky case is when we have exactly $$$2$$$ vertexes with outside edges. In this case, let's root our current tree (we build a tree using only vertexes from the set and edges from the original tree) and root this tree by its centroid. Then suppose two vertexes with outside edges are $$$u, v$$$. Let's take $$$LCA(u, v)$$$ as our new splitting vertex and run the recursive process for each of its subtrees.

Now let's talk about the complexity. In the first case when we have $$$\leq 1$$$ vertexes with outside edges, each size of subtree is $$$\leq \frac{s}{2}$$$ where $$$s$$$ is original size of the tree. In the second case, every subtree of $$$LCA(u, v)$$$ has size $$$\leq \frac{s}{2}$$$ because the tree was rooted by its centroid, and each one of those subtrees has obviously $$$\leq 2$$$ vertexes. However, the upper subtree of $$$LCA(u, v)$$$'s size might be $$$\geq \frac{s}{2}$$$, however, this upper tree would have only one vertex with edge going outside (which is connected to $$$LCA(u, v)$$$), so after another iteration its size will decrease by factor of two because it's the first case. So the size of the tree decreases by factor of two in every two operations, therefore the tree's height is $$$\leq 2 \cdot log_2(n)$$$, and the final complexity is $$$O(n \cdot log_2(n))$$$.

Furthermore, the obtained decomposition still has all the properties of usual centroid decomposition.

I think this technique can be called "centroid pro max". Suggest other names if you have ideas!