### NeoYL's blog

By NeoYL, 3 months ago,

Below is a variant of the problem:

Given that there are $N$ ($1 \leq N \leq 300$) nodes.

An integer $L$ ($L \leq N$) is also given.

Find the number of ways to construct a graph with the following properties:

1. The graph is a forest

2. The largest connected component's size = L

3. All nodes have degree $\leq 3$

4. There isn't any repeated edge

Credits to -is-this-fft-, for the amazing cost function in the comments section. And his blog here: https://codeforces.com/blog/entry/123211

The solution is pretty cool and leave a like for him too!

Solution

Note: I won't delete a blog that has contents that might act as a learning material for anyone.

• +42

 » 3 months ago, # |   0 Please leave a like if you loved the idea of the problem!
 » 3 months ago, # |   +11 I didn't really read most of what you wrote but here is how I'd solve this.Let's first learn to count the number of labeled trees with $k$ vertices where each vertex has degree at most 3. We'll use Prüfer sequences. A Prüfer sequence of a tree with $k$ vertices is an array consisting of $k-2$ entries. Importantly, each tree corresponds to exactly one sequence and vice versa. Also, every vertex $u$ appears in the sequence exactly $\mathrm{deg}(u) - 1$ times.So we need to count the number of arrays consisting of $k - 2$ entries such that every vertex appears in the array 0, 1 or 2 times. We will do that with DP: let $\mathrm{dp}[i][j]$ be the number of sequences where we have already placed the first $i$ vertices that have length $j$ now. We'll try to place the $i$-th vertex now. A sequence of $j$ elements has $j + 1$ "slots" where we could insert the instances of the $i$-th vertex. So, $\mathrm{dp}[i][j]$ contributes once to $\mathrm{dp}[i + 1][j]$; $(j + 1)$ times to $\mathrm{dp}[i + 1][j + 1]$; $\binom{j + 1}{2}$ times to $\mathrm{dp}[i + 1][j + 2]$. You can calculate this DP in $O(n^2)$ time and you'll be interested in the value of $\mathrm{dp}[k][k - 2]$ for every $k$. And given what you wrote above, I believe you can take it from here.
•  » » 3 months ago, # ^ |   0 Woah, that's cool I didn't really think deep for dp on prufer sequence. Thx for answering. Also I believe that k=1 is a corner case. My blog was long just because I wanted to show some of my ideas, which might be useful for others.