P8820 [CSP-S 2022] Data Transmission

Please do not abuse the judging of this problem, otherwise your account may be banned.

Xiao C is designing a routing system for a computer network. The test network has $n$ hosts, numbered $1 \sim n$. These $n$ hosts are connected by $n - 1$ network cables; the $i$-th cable connects hosts $a_i$ and $b_i$. It is guaranteed that any two hosts are connected directly or indirectly through a finite number of cables. Due to transmission power limits, host $a$ can directly send information to host $b$ if and only if the two hosts are connected directly or indirectly by a path that uses at most $k$ cables. In a computer network, data transmission often requires several forwards. Suppose Xiao C needs to send data from host $a$ to host $b$ ($a \ne b$). He will choose several hosts for transmission $c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$, and forward as follows: for all $1 \le i < m$, host $c_i$ directly sends information to $c_{i + 1}$. Each host needs some time to process information. The $i$-th host needs $v_i$ units of time. Data transmission in the network is very fast, so the transmission time can be ignored. Therefore, the total time cost of the above process is $\sum_{i = 1}^{m} v_{c_i}$. There are $Q$ data sending requests in total. In the $i$-th request, data is sent from host $s_i$ to host $t_i$. Xiao C wants to know, for each request, the minimum number of time units needed to complete the transmission.

The first line contains three positive integers $n, Q, k$, denoting the number of hosts, the number of requests, and the transmission parameter, respectively. It is guaranteed that $1 \le n \le 2 \times {10}^5$, $1 \le Q \le 2 \times {10}^5$, $1 \le k \le 3$. The second line contains $n$ positive integers; the $i$-th integer is $v_i$, and it is guaranteed that $1 \le v_i \le {10}^9$. The next $n - 1$ lines; the $i$-th line contains two positive integers $a_i, b_i$, indicating a network cable connecting hosts $a_i$ and $b_i$. It is guaranteed that $1 \le a_i, b_i \le n$. The next $Q$ lines; the $i$-th line contains two positive integers $s_i, t_i$, indicating a request to send data from host $s_i$ to host $t_i$. It is guaranteed that $1 \le s_i, t_i \le n$ and $s_i \ne t_i$.

Output $Q$ lines. Each line contains one positive integer, the minimum number of time units needed to complete the $i$-th request.

【Sample Explanation #1】 For the first request, since hosts $4$ and $7$ require at least $4$ cables to connect, data cannot be transmitted directly between the two hosts, so at least one forward is required. Let it be forwarded once at host $1$. It is easy to see that both host $4$ and host $7$ are within two cables from host $1$, and host $1$ has a processing time of only $1$, the minimum among all hosts. Therefore, the minimum transmission time is $4 + 1 + 7 = 12$. For the third request, since hosts $1$ and $2$ are connected by only $1$ cable, direct transmission is optimal, and the minimum transmission time is $1 + 2 = 3$. 【Sample #2】 See the attachments `transmit/transmit2.in` and `transmit/transmit2.ans`. This sample satisfies the limits of test point $2$. 【Sample #3】 See the attachments `transmit/transmit3.in` and `transmit/transmit3.ans`. This sample satisfies the limits of test point $3$. 【Sample #4】 See the attachments `transmit/transmit4.in` and `transmit/transmit4.ans`. This sample satisfies the limits of test point $20$. **Constraints** For all testdata, it is guaranteed that $1 \le n \le 2 \times {10}^5$, $1 \le Q \le 2 \times {10}^5$, $1 \le k \le 3$, $1 \le a_i, b_i \le n$, $1 \le s_i, t_i \le n$, and $s_i \ne t_i$. | Test point | $n \le$ | $Q \le$ | $k =$ | Special property | |:-:|:-:|:-:|:-:|:-:| | $1$ | $10$ | $10$ | $2$ | Yes | | $2$ | $10$ | $10$ | $3$ | Yes | | $3$ | $200$ | $200$ | $2$ | Yes | | $4 \sim 5$ | $200$ | $200$ | $3$ | Yes | | $6 \sim 7$ | $2000$ | $2000$ | $1$ | No | | $8 \sim 9$ | $2000$ | $2000$ | $2$ | No | | $10 \sim 11$ | $2000$ | $2000$ | $3$ | No | | $12 \sim 13$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $1$ | No | | $14$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $2$ | Yes | | $15 \sim 16$ | ${10}^5$ | ${10}^5$ | $2$ | Yes | | $17 \sim 19$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $2$ | No | | $20$ | $5 \times {10}^4$ | $5 \times {10}^4$ | $3$ | Yes | | $21 \sim 22$ | ${10}^5$ | ${10}^5$ | $3$ | Yes | | $23 \sim 25$ | $2 \times {10}^5$ | $2 \times {10}^5$ | $3$ | No | Special property: it is guaranteed that $a_i = i + 1$, and $b_i$ is chosen uniformly at random from $1, 2, \ldots, i$. Translated by ChatGPT 5