P5547 [BJ United Round #3] Three-Color Tree

Please count the number of **unlabeled unrooted trees** with $n$ nodes that satisfy the following requirements: - Each node has one of three colors: red, blue, or yellow. - The degree of a red node is at most $4$, and the degrees of blue and yellow nodes are both at most $3$. - Yellow nodes cannot be adjacent. Note that the meaning of an **unlabeled unrooted tree** is: if two trees can be made identical by renumbering the nodes so that the corresponding nodes have the same colors and the corresponding edges match, then they are considered the same tree. The answer should be taken modulo the prime number $p$ given in the input.

Two positive integers $n,p$, with the meanings as described above.

One integer, representing the number of valid trees modulo $p$.

For $100\%$ of the testdata, it is guaranteed that: $1\le n \le 3000$. $9\times 10^8 \le p \le 1.01 \times 10^9$. It is guaranteed that $p$ is prime. By: EntropyIncreaser Translated by ChatGPT 5