Hello UOJ! 非常感谢 UOJ community for the great contests!!

• Problem: https://uoj.ac/contest/81/problem/793
• Editorial: https://qingyu.blog.uoj.ac/blog/8116
• Solution by zhoukangyang: https://www.cnblogs.com/zkyJuruo/p/17136175.html

I present a solution which is kind of a combination of the above two, so it might be essentially the same with them, but I hope it contains something valuable (e.g. easier to come up with).

First of all we need the very clever correspondence to the forest problem, described in 算法二点五 of the editorial.

To count the coloring ways, we can assign weight to each 道路 (thus to each edge), with the base answer $k^{m+1}$. The weight depends on the number of non-final 接口s among the two 接口s created on the 道路. Letting this number be $q \in \{0,1,2\}$, the weight $a_q$ is \begin{equation} a_0 = 1 - \frac{1}{k}, \quad a_1 = 1 - \frac{2}{k}, \quad a_2 = 1 - \frac{2k-3}{k(k-1)}. \end{equation} These are based on the fact that $k$ colors are symmetric. Through the correspondence, $q$ for edge $\{u,v\}$ is the number of satisfied conditions among the following:

• $\exists w$ s.t. edge $\{u,w\}$ exists and $w$ is on the arc from $u$ to $v$ clockwise.
• $\exists w'$ s.t. edge $\{v,w'\}$ exists and $w'$ is on the arc from $v$ to $u$ clockwise.

Now let's count the trees. We define two GFs (with $x$ counting the vertices) for the following cases:

• $f$: The root will be attached to a parent which becomes the final 接口.
• $g$: The root will be attached to a parent which becomes the non-final 接口.

For the whole tree, we can fix a root then its children are nothing or $f, g, \ldots, g$, so the GF we want to find is $h = x \left( 1 + \frac{f}{1-g} \right)$.

And we formulate the recurrence by noticing that the edge to the parent will separate the region into two parts:

\begin{align*} f &= x \left( a_0 + a_1 \frac{f}{1-g} \right) \frac{1}{1-g} \\ g &= x \left( a_1 + a_2 \frac{f}{1-g} \right) \frac{1}{1-g} \end{align*}

Solving the second one in $f$ and plugging it into the first one gives an equation in $g$ of degree $5$, so we can apply the Newton method... In fact we can be lazy here because these behave well for online convolution ($[x^n] f$ or $[x^n] g$ on the left-hand side is determined by $f \bmod x^n$ and $g \bmod x^n$ on the right-hand side), so $f$ and $g$ can be calculated in $O(n \log(n)^2)$ time. The implementation is easy with fjzzq2002's cool template https://fjzzq2002.blog.uoj.ac/blog/7281 (sorry I am so lazy to just copy it...).

Then we can find $h$, and finally the answer for the forest case is (magically) $\dfrac{1}{n+1} \displaystyle\binom{n+1}{n-m} [x^n] h^{n-m}$; This is well explained in zhoukangyang's solution.

My submission: https://uoj.ac/submission/625385

I wonder if the equations above for $f$ and $g$ can lead to a simpler/faster algorithm like zhoukangyang's.

By the way, this solution is relatively simple if we just want to count the trees without considering the coloring (i.e. when $a_q = 1$): since $f = g$ we have $f = x \dfrac{1}{(1-f)^2}$. By Lagrange inversion, \begin{align*} [x^{n+1}] h &= [x^n] \frac{1}{1-f} \\ &= \frac{1}{n} [x^{n-1}] \left( \frac{1}{1-x} \right)' \left( \frac{1}{(1-x)^2} \right)^n \\ &= \frac{1}{n} [x^{n-1}] \frac{1}{(1-x)^{2n+2}} \\ &= \frac{1}{n} \binom{3n}{n-1} \end{align*} and this agrees with https://oeis.org/A001764.