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}
)
for your so much efforts and time .