CSES Tree Matching

Tree Matching solved with dynamic programming

Let's define :

$dp(P,0)$ : The max matching number that DOES NOT INCLUDE node P.

$dp(P,1)$ : The max matching number that INCLUDES node P.

Therefore, the max matching set size at node P will be $max[ dp(P,0) ,  dp(P,1) ]$

Then, let's go more deeper. How can we define $dp(P, 0)$?

It will be the max matching number of all the trees starting at the children nodes ($C_1, C_2...$) of node P. That is:

$$dp(P,0) = \sum_{i \in children}max[ dp(C_i, 0), dp(C_i, 1)]$$

 $dp(P, 1)$ will be selecting a children node and calculate its optimal, then loop through all the children nodes and compare which children node picked will be the maximum.

$$dp(P,1) = \underset{t \in children}{max}\left ( \left \{ \sum_{i \in children}max[ dp(C_i, 0), dp(C_i, 1)]\right \} - max[ dp(C_t, 0), dp(C_t, 1) ] + dp(C_t,0) + 1 \right )$$

$$=\underset{t \in children}{max}\left ( dp(P,0)  - max[ dp(C_t, 0), dp(C_t, 1) ] + dp(C_t,0) + 1 \right )$$