Instead of counting how many trees can be decomposed into paths, we count how to decompose a tree into such paths. Of course, there are multiple ways to decompose a tree into paths, so we attach a suitable weight to each decomposition to find the correct count.

First, consider how many ways there are to decompose a tree into paths.

Look at a vertex \(v\). For each edge \(v \to w\) going from \(v\), the number of “leftover vertices” on the \(w\) side is uniquely determined. An edge with \(x\) leftover vertices and an edge with \(y\) leftover vertices can be matched when \(x+y=2K+1\), so if we let \(C_{v,x}\) be the number of edges around \(v\) with leftover count \(x\), we must have \(C_{v,2K+1-x} = C_{v,x}\), and the number of ways to match them up is \(C_{v,x}!\).

Also, it can be seen that if we determine the matching for all \(v\) and \(1 \leq x \leq K\), it is possible to take \(N\) paths according to the matching. Thus, if we multiply the weight by \(1 / C_{v,x}!\) for all \(v\) and \(1 \leq x \leq K\), we can negate the duplicates arising from counting paths.

However, directly multiplying by \(1 / C_{v,x}!\) for each tree is difficult, so we transform the problem again.

To make each tree count exactly once, we would like to multiply by \(1 / C_{v,x}!\) for each \(v\) and \(x\). Directly assigning \(1 / C_{v,x}!\) to each tree is difficult, so we transform the problem again.

Define two paths \(p\) and \(q\) to be directly connected if and only if they intersect at a vertex other than their endpoints, and at that vertex, it is possible to swap those paths (that is, swap the edge-to-edge matchings described above). Also, a set of paths \(S\) is connected if, for any two paths \(p, q \in S\), we can travel from \(p\) to \(q\) along edges in \(S\) that are directly connected.

Under this definition of connectedness, we partition the paths into several groups. Each group must be connected, but edges that are directly connected need not belong to the same group.

Observe this grouping around a vertex. Let \(X\) be the set of edges with \(x\) leftovers \(x\) when seen from \(v\), and \(Y\) be the set of edges with \(2K+1-x\) leftovers when seen from \(v\). We partition \(X\) and \(Y\) according to the respective grouping of paths, and say we get \(X = X_1 \sqcup \cdots \sqcup X_s\) and \(Y = Y_1 \sqcup \cdots \sqcup Y_s\). (Here, \(X_i\) and \(Y_i\) belong to the same group. Clearly, \(|X_i| = |Y_i|\).) Now, consider assigning a weight \(W \lbrack |X_i| \rbrack\) to each group. We will set the values of \(W\) to adjust the weights of trees.

If we fix a decomposition into paths and observe the edges with \(x\) or \(2K+1-x\) leftovers around \(v\), there are \(C_{v,x}\) paths passing \(v\). When these paths are further partitioned into groups, we will multiply each group by the weight \(W \lbrack |X_i| \rbrack\), and we want the total weight to be \(1 / C_{v,x}!\). It is possible to actually construct such a \(W\); it cannot be expressed in a closed form, but can be computed using fps log.

Consider finding the answer using this \(W\). Let \(A_n\) be the sum of weights over all groups of exactly \(n\) paths. We then split the problem into two steps:

1. Compute \(A_1, A_2, \dots, A_N\).
   
2. Use \(A_1, A_2, \dots, A_N\) to compute the final answer.

Consider Step 1.

A group of \(n\) paths is a tree with \(n(2K+1) + 1\) vertices. Consider assigning levels \(0,1,\dots,2K+1\) to the vertices. There are edges only between adjacent levels, and there are two ways to assign levels for a tree.

Ignore the vertices of levels \(0\) and \(2K+1\), which are leaves. Let \(M = 2K\) and focus only on vertices at levels \(1, 2, \dots, M\). There are \(n(M-1)+1\) vertices. Now, we want to find the answer to the following subproblem multiplied by a constant factor:

Subproblem

Consider weighted counting of spanning trees of a bipartite graph. We have the existing \(n(M-1)+1\) vertices on the \(L\) side, and \(n\) vertices corresponding to the \(n\) paths on the \(R\) side. An edge \((l,r)\) means that vertex \(l\) belongs to path \(r\).

What is the sum of weights of all spanning trees of this bipartite graph where:

• Every vertex on the \(R\) side mush have degree \(M\);
• If a vertex on the \(L\) side has degree \(i\), the weight is multiplied by \(W \lbrack i \rbrack\).

Let us solve this subproblem. Consider a rooted tree rooted at a right-side vertex. The answer depends on whether the tree is a proper subtree (that is, whether the parent exists), so we define the following:

• \(A(x)\): The generating function for the answer (with \(\frac{n A_n}{n! (n(M-1)+1)!}\) as coefficients)
• \(B(x)\): The generating function for the sequence where the sum of weights over trees with parents is multiplied by \(\frac{n}{n! (n(M-1)+1)!}\)

Then, the generating function for the case where a child with a root has \(n\) children can be represented as:

\[U(x) = \sum_{n \geq 0} \frac{W_{n+1}}{n!} x^n.\]

Thus, if we define:

\[S(x) = \frac{U^M}{M!}, \quad T(x) = \frac{U^{M-1}}{(M-1)!},\]

we obtain the relationship:

\[ \begin{aligned} A(x) &= x \, S(B(x)), \\ B(x) &= x \, T(B(x)). \end{aligned} \]

Hence, if we can find the inverse function of \(B(x)\) and find \(A(x)\) by function composition, we can compute \(A(x)\) in \(\mathrm{O}(N \log^2 N)\) time. (One can also do a small transformation to find the coefficients of \(A(x)\) with one power projection to do this part two times faster.)

• Inverse functions, function composition, and power projection: Kinoshita (noshi91) and Li (Elegia) found in 2024 an algorithm to compute function composition and inversion of a function (of degree \(N\)) in \(\mathrm{O}(N \log^2 N)\) time. For references, see Kinoshita and Li’s paper and related articles on CodeForces, which maspy’s article summarizes with relevant links.

Next, consider Step 2.

Now, we know \(A_n\), the sum of weights over all groups of \(n\) paths. Because we can ignore the interference of different groups, we can compute the coefficients for merging based only on the sizes of the groups. We will omit the details, but if \(F(x)\) is the generating function for the sequence where the answer is multiplied by \(\frac{n(2K+1)+1}{(n(2K+1)+1)!}\), we have:

\[ F(x) = \exp\!\biggl(\!\sum_{i=1}^\infty \frac{A_i}{((2K+1)i)!} \, x^i \, F(x)^{(2K+1)i}\biggr). \]

One could apply Newton’s method to this formula as is (performing the Kinoshita–Li function composition internally), but a small rearrangement yields a formula \(x F^{2K+1} = x G(x F^{2K+1})\) using a function \(G(x)\), allowing us to compute \(F\) using the Kinoshita–Li inverse function, which would be easier.

By implementing these steps, one can solve the problem in \(\mathrm{O}(N K + N \log^2 N)\) time, which is sufficiently fast.