Please reply if anything requires more explanation. I’ll add it if I find it necessary.

# Explanation

Let dp[u][D] be the number of ways to finish the journey if you start at node number u and take D days to finish the journey ( We won’t be explicitly calculating this, this is just an intermediate step for the actual solution ).

When at node u, if we want to spend total D days, we can spend r days visiting tourist attractions (where 0 \le r \le D-1), and then go to any v \in \text{adj}[u] (taking up one day), and continue the journey form v. Here, adj[u] is the set of all vertices v such that (u,v) is an edge. On each day, we have L[u] choices of tourist attractions to visit, so number of ways to visit tourist attractions is L[u]^r.

So, dp[u][D] can be expressed recursively as \displaystyle dp[u][D] = \sum_{v \in \text{adj}[u]} \sum_{r=0}^{D-1} L[u]^r dp[v][D-1-r]

Also, dp[n][D] = L[n]^D

This is clearly a convolution. If we create generating functions ( 1 2 ) G_u(x) = \displaystyle \sum_{r=0}^{\infty} dp[u][r] x^r, we can recursively express the dp relation as

G_u(x) = \displaystyle \frac{x}{1-L[u]x} \sum_{v \in \text{adj}[u]} G_v(x)

with base case G_n(x) =\displaystyle \frac{1}{1 - L[n]x}

Now, looking at the expression here, we can say that the denominator will be exactly \displaystyle \prod_{\text{there exists a path from u to v}} (1 - L[v]x).

You *can* prove this by induction, but I won’t because it’s very straightforward, and *should be* intuitively obvious.

Also, the highest power of x in the numerator is exactly 1 less that that of denominator, since for G_n(x), it is 1 less and at each subsequent step we are multiplying numerator and denominator by equal powers of x.

Now, we can apply a method that is seen in solving linear homogenous recurrences

Since we know the factorisation of the denominator, we can do a partial fraction decompostion of the G_u(x)

Let \{l_1,l_2,l_3 \cdots l_k\} be the * distinct* values of L[u] for all the nodes, where L[u] = l_i for m_i different values of u i.e. its m_i is the multiplicity of l_i.

We can now assume that G_u(x) for any u is of the form

\displaystyle \frac{a_{1,1}}{(1 - l_1x)^1} + \frac{a_{1,2}}{(1 - l_1x)^2} \cdots \frac{a_{1,m_1}}{(1 - l_1x)^{m_1}} + \\ \frac{a_{2,1}}{(1 - l_2x)^1} + \frac{a_{2,2}}{(1 - l_2x)^2} \cdots \frac{a_{2,m_2}}{(1 - l_2x)^{m_2}} + \\ \vdots \\ \frac{a_{k,1}}{(1 - l_kx)^1} + \frac{a_{k,2}}{(1 - l_kx)^2} \cdots \frac{a_{k,m_k}}{(1 - l_kx)^{m_k}} ,

which is exactly n terms.

We can now represent G_u(x) as n coefficients of the form a_{u,i,j}.

To calculate G_u(x), we first calculate

\displaystyle \sum_{v \in \text{adj}[u]} G_v(x) = \sum_{v \in \text{adj}[u]} \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{a_{v,i,j}}{(1 - l_ix)^p} = \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{ \sum_{v \in \text{adj}[u]} a_{v,i,j}}{(1 - l_ix)^p} = \sum_{i=1}^{k} \sum_{p=1}^{m_i} \frac{T_{u,i,j}}{(1 - l_ix)^p}.

where \displaystyle T_{u,i,j} = \sum_{v \in \text{adj}[u]} a_{v,i,j}\ . We can calculate this in O(|\text{adj}[u]|N), which when added up for each u comes out to be O(MN).

We can easily derive expressions for a_{u,i,j} in terms of T_{u,i,j}, l_i \ \text{and}\ L[u]. There are 2 expressions, one for when L[u] = l_i and one for L[u] \neq l_i.

I won’t be providing these expression as they are fairly ugly and take away from the bigger picture of the overall solution. You can refer to my code for them ( as I said it’s not pretty ).

Knowing this representation of G_u(x), we can calculate dp[u][D] using the binomial theorem as \displaystyle \sum_{i=1}^{k} \sum_{p=1}^{m_i} a_{u,i,p} \cdot l_i^D \cdot \binom{D+p-1}{p} in O(N \log D)

We are of course interested in dp[1][D] for each query.

# Overall complexity

O(NM + QN \log D)

# Example

As an example, I will calculate G_1(x) for the sample test case in original problem statement.

\displaystyle G_4(x) = \frac{1}{1-7x}

\displaystyle G_3(x) = \frac{x}{1-6x} \left( \frac{1}{1-7x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_2(x) = \frac{x}{1-6x} \left( \frac{1}{1-7x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_1(x) = \frac{x}{1-2x} \left( \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) + \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) \right) \\ = \frac{x}{1-2x} \left( \frac{-2}{1-6x} + \frac{2}{1-7x} \right) \\ = -\frac{1}{2} \left( \frac{1}{1-6x} \right) + \frac{2}{5} \left( \frac{1}{1-7x} \right) + \frac{1}{10} \left( \frac{1}{1-2x} \right)

So, number of ways of finishing the journey in D days is \displaystyle \frac{(-5)\cdot 6^D + 4\cdot7^D + 2^D}{10}

# Another Example

Another example, which has multiplicity greater than 1 for a term.

I’ll take the same testcase as before but take L[4] = 6 and L[3] = 7 instead.

\displaystyle G_4(x) = \frac{1}{1-6x}

\displaystyle G_3(x) = \frac{x}{1-7x} \left( \frac{1}{1-6x} \right) = \frac{-1}{1-6x} + \frac{1}{1-7x}

\displaystyle G_2(x) = \frac{x}{1-6x} \left( \frac{1}{1-6x} \right) \\ = -\frac{1}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2}

\displaystyle G_1(x) = \frac{x}{1-2x} \left( \left( -\frac{1}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2} \right) + \left( \frac{-1}{1-6x} + \frac{1}{1-7x} \right) \right) \\ \ \\ = \frac{x}{1-2x}\left( -\frac{7}{6} \frac{1}{1-6x} + \frac{1}{6} \frac{1}{(1-6x)^2} + \frac{1}{1-7x} \right ) \\ \ \\ = \frac{9}{80} \frac{1}{1-2x} + \frac{1}{5} \frac{1}{1-7x} + \frac{-17}{48} \frac{1}{1-6x} + \frac{1}{24} \frac{1}{(1-6x)^2}