343. 【22CSPS提高组】数据传输(transmit) 中等

小 C 正在设计计算机网络中的路由系统。 测试用的网络总共有 $n$ 台主机，依次编号为 $1$ ∼ $n$。这 $n$ 台主机之间由 $n − 1$ 根网线连接，第 $i$ 条网线连接个主机 $a_i$ 和 $b_i$。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机 $a$ 能够直接将信息传输给主机 $b$ 当且仅当两个主机在可以通过不超过 $k$ 根网线直接或者间接的相连。 在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b(a≠b)$，则其会选择出若干台用于传输的主机 $c_1$ = $a$, $c_2$, · · · , $c_{m−1}$, $c_m$ = $b$，并按照如下规则转发：对于所有的 $1 ≤ i < m$, 主机 $c_i$ 将信息直接发送给 $c_{i+1}$。 每台主机处理信息都需要一定的时间，第 $i$ 台主机处理信息需要 $v_i$ 单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为 $\sum_{i=1}^{m}v_{c_i}$。 现在总共有 $q$ 次数据发送请求，第 $i$ 次请求会从主机 $s_i$ 发送数据到主机 $t_i$。小 C想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。