As a backstory: I was solving [a past atcoder problem](https://atcoder.jp/contests/arc101/tasks/arc101_c), found some cubic DP-solution (different from the editorial one) being something like "$dp[v][x]$ — we have $X$ non-matched vertices in $V$'s subtree, its child $TO$ has $Y$ ones, we want to choose some $Z$ of $X$ and $Z$ of $Y$ to match them and update". However, that's too slow to get accepted.↵
↵
Thus, the solution can be optimized if, for example, we can precalculate some $VAL[x][y]$, meaning number of matchings (**not necessarily maximum ones**) in a complete bipartite graph having left part of size $X$ and right part of size $Y$, faster that $N^3$. The obvious formula would be to fix $Z$ nodes we match and count the $VAL[x][y]$ through $C(n, k)$ which I have not been capable neither to find any paper related to it on the Internet nor to get to any observation.↵
↵
Are there any kind of resources to seek at, or, perhaps, some ideas on getting the precalcution in time?
↵
Thus, the solution can be optimized if, for example, we can precalculate some $VAL[x][y]$, meaning number of matchings (**not necessarily maximum ones**) in a complete bipartite graph having left part of size $X$ and right part of size $Y$, faster that $N^3$. The obvious formula would be to fix $Z$ nodes we match and count the $VAL[x][y]$ through $C(n, k)$ which I have not been capable neither to find any paper related to it on the Internet nor to get to any observation.
↵
