この問題は有向非巡回グラフ（DAG）上のDPを問います。

愚直に実装してみたいところですが辺の本数は多くて $10^5$ を超え、かつ移動する経路の数は膨大です。
なのでこのアプローチでは到底、答えを得ることは困難であることが分かります。

以下、$W=w_j, R=r_j, F=f_j\ (1\le j\le Q)$ としてクエリ $1$ 個当たりの処理の説明を行います。

I.「走る」回数の条件

まずはこの問題に書かれた操作において重要な性質があります。
それは一つの移動方法に対して、「どの道の移動で」走ったか（または歩いたか）の情報は必要なく、「歩いた」回数および「走った」回数さえわかればよいことになります※1。
さらにその $2$ つの情報は、その移動で何回移動を行うか、という情報から「走った」回数だけを知るだけでよいことになります。

これを数式に表してみましょう。ある一つの移動方法において、その移動回数は $m$ であったとします。
この移動において走った回数を $c$ とすれば（歩いた回数は $m-c$ と表せます）、本問題で満たすべき条件式は次のように立式できます：

• $cR+(m-c)W\le T$

これを変形することによって $c\ge \cfrac{mW-T}{W - R}$ を得ます。つまりその移動方法において、走る回数は $\Bigg\lceil \cfrac{mW-T}{W - R}\Bigg\rceil$（以下、この値を $c_l$ とします）回以上でないと条件を満たすような移動を行えないということを意味します。
さらに移動回数は $m$ 回ということから、$\cfrac{mW-T}{W - R}\le c\le m$ が成り立ちます。これによって走る回数 $c$ に対する条件式を表すことができました。

この条件式を用いることによって、$m$ の値が固定できれば、その移動方法において走る移動が $c_l$ 回以上あるような方法すべてが、今回の問題を満たすようなものになります。

II. $m$ の値の求め方とDPの立式

上で立式した条件式において、$m$ の値を固定しないと $c$ の具体的な値の条件を計算できません。そのため $m$ を求める必要があります。

今回の制約から、与えられる街の構造は有向非巡回グラフ（DAG）とみなすことができます。このグラフ構造では、有向閉路が存在しないことが保証されています。
つまり、ある一つの移動方法において $m$ の値は一意に定まることになります※2。

DAGであれば、実は「街 $1$ から街 $k\ (1\le k\le N)$ までに移動する方法の数（走る・歩くの要する時間は考慮しない）を求める」といった問題をDPによって求めることができます※3。
またどのような移動であったとしても、ある二つの移動方法において移動回数 $m$ が変わらないなら、このDPによって求める「移動方法の個数」を使って容易に計算することができます。

以上、セクション I, II. において $m,c$ の値を固定することにより、今回解く問題は一つの移動方法に対して、次のように言い換えることができます：

• 問題★：$m$ 回の移動の中で $c_l=\lceil \frac{mW-T}{W - R} \rceil$ 回以上 $m$ 回以下※4だけ、「走る」移動を行うようにする移動の選び方は何通り？

これは二項係数を用いて計算することが可能です。

このセクション内で本質的な問題は $m$ の値を求めることであり、実はその値は $m=0,1,\dots,N-1$ と表せます。そしてこの値を $t$ として、次のようなDP配列を定義します：

• $\text{dp}[v][t]:=$ 頂点 $1$ から頂点 $v$ までちょうど $t$ 個の点を経由することによって到達できる方法の数

これを計算することによって、同じ $m$ 回の移動であったとしても移動の操作は変わらないことから、全体における移動の選択方法の計算を行うことができます。
つまり、ちょうど $t$ 回の移動となるような経路が $\text{dp}[v][t]$ 通りだけ存在する、ということを用いて、後に示す移動の選び方の組み合わせの個数が容易に計算できるようになります。

ではこのDPの話を深堀りしていきましょう。
まず初期化は、今回求めるものは組み合わせの総数なので

• $\text{dp}[0][0] = 1$
• $\text{dp}[i][j]=0\ (0\le i,j\le N, i\ne 0\cap j\ne 0)$

となります※5。

次に遷移について、$G$ はDAGなのでトポロジカルソートによって、一つの頂点からどのような経路をたどるかは一意に定まります※6。
この一意性を利用すれば、$G$ においてトポロジカルソート順に並びかえた頂点列 $(V_1,V_2,\dots,V_N)$ として、ある頂点 $v$ に隣接する頂点集合 $\{u_1,u_2,\dots, u_n\}$ とすれば、遷移式は

• $\text{dp}[u_i][t + 1] = \text{dp}[u_i][t + 1] + \text{dp}[V_i][t]\ (1\le i\le N, 0\le t\lt N)$

となります。ここで $t$ は移動回数を表すので $0\le t\lt N$ となります。
このDPによって $O(N^3)$ で計算をすることができます。厳密には、頂点 $i$ の頂点の次数 $e_i$ とすれば $O(N^2\times \max(e_i))$ と表すことができます。今回、制約から「任意の街について、街からつながる道は $10$ 本以下」となっているため、時間制限に間に合います。

この計算の結果、求めるのに欲しい情報は $\text{dp}[F][k]\ (0\le k\le N)$ となります。
$k$ はそのまま移動回数 $m$ の値となる他、前に示した通り $\text{dp}[F][k]$ は移動の方法の数となります。これによって求めたい値をまた取得することができました。

III. 求める値の立式

セクション I. で求めた条件式 $\cfrac{mW-T}{W - R}\le c\le m$ において、II. によって $m$ が固定できるので $c$ の値の範囲を具体的な数値を代入しながら計算することができます。

以上の情報を通して、ある $1$ つの移動方法（この時の移動回数を $m$ とします）に対するこの組み合わせの答えは、条件式に基づいた下限 $c_l$ 、上限 $c_u(=m)$ として、和の法則よりセクション II. で示した問題★の答えは $\displaystyle \sum^{c_u}_{k=c_l} C(m,k)$ となります。
そして $0\le t\le N$ において $\text{dp}[F][t]$ 通りだけ同じ移動回数の移動の選び方が存在するので、任意の $1$ つの $t$ における答えは $\text{dp}[F][t]\times \displaystyle \sum^{c_u}_{k=c_l} C(m,k)$ となります。これが全体の「経路の選び方」の総数です。

$t$ 回の移動に関して、「ある移動の仕方を選ぶ」場合に対する $c$ の答えを $c_t$ で表現して、$t=0,1,2,\dots,N$ に対して $(c_0,c_1,\dots, c_N)$ とすれば、求める値は

• $\displaystyle\sum^{N}_{t=0} \Bigr( \bigr(\sum^{t}_{k=c_t} C(m_t, k)\bigl)\times \text{dp}[F][t] \Bigl)$

と表せます。

しかし今回、上の計算値を $Q$ 回のクエリに答える必要があります。
愚直に上の値を計算していると最悪 $O(N^2)$ だけ要することになり、すべてのクエリを制限時間内に処理できなくなってしまいます。

そこで累積和を使って、$\sum^{t}_{k=c_t} C(m_t, k)$ の計算を高速化させることを考えます。
これは $m_t=m$ と固定して $S_i=C(m, 0)+C(m, 1)+\dots +C(m, i)=\displaystyle\sum^{i}_{k=0} C(m, i)$ と定義し、

• $\displaystyle\sum^{t}_{k=c_t} C(m, k)=\sum^{t}_{k=0} C(m, k) - \sum^{c_t - 1}_{k=0} C(m, k)=S_t-S_{c_t-1}$
• $S_{i+1}=S_i+C(m, i)$

の関係式を用いることにより、$\displaystyle\sum^{t}_{k=c_t} C(m_t, k)$ の計算を $O(1)$ で処理できるようになります※7。

以上でこの値を求めることでこの問題を正解することができます。
これにより、トポロジカルソートやDPを行う前処理で、頂点 $v$ の次数 $e_v$ とおいて $O(N^2 \max(e_v))$、クエリ $1$ 回の処理で $O(N)$ だけ要することになります。

ゆえに本問題は $O(N^2 \max(e_v)+NQ)$ で解くことができました。本ページ最下部に解答例（C++）を示しています。

※1
その移動方法で走る回数が変わらない限り、どのように道を使って移動しようと結果的に要する時間は変わりません。この性質を利用しています。

※2
制約から「同じ街は $2$ 回以上訪れることはできない」と書かれています。この情報から、ある街から街まで移動する方法は一意に定まり、他の移動方法は存在しないことになります。
これは、街 $i$ から街 $j$ まで $m$ 個の街を経由して移動する方法の数は一意に定まるということを意味しています（ $1\le i,j\le N,\ 0\le m\lt N$ ）。

※3
DPは、遷移の形がDAGとして表現できるような問題で扱うことができます（逆にそうでないような問題は適用できない...？）。
今回は明らかにDAG構造を成しているため、適用できます。

※4
一般に「$a$ 回以上 $b$ 回の移動の方法は何通りか」などといった、回数が範囲で示されている場合は「それぞれちょうど $a,a+1,\dots,b$ 回の移動を行った場合の方法は何通りか」のような形で、ちょうど～回といった文に言い換えることができます。今回でもこれを利用して解きます。

※5
$i=j=0$ の場合に $1$ となるのは、頂点 $1$ から頂点 $1$（移動回数 $t=0$）に移動する方法の数は明らかに $1$ 通りであるためです。このとき $i,j$ は0-indexedであることに注意してください。

※6
厳密にはトポロジカルソートを行った結果は一意とは限らない可能性もあります（諸説あり）。しかしソートをされているならどの順番であったとしても正確な答えは求められることは保証されるので、今回のアプローチは適切です。

※7
すべての $m$ に対して前処理を行うので、前処理で最悪 $O(N^2)$ だけかかります。