1455 . 拉完了
TopCoder
Tags
Description
一個風和日麗的早上，因為作息很爛所以喂喂在宿舍裡睡覺。
從新竹搬到台北之後，喂喂感受到台北的食物非常好吃，而且每個捷運站附近都有一些好吃的食物。某天，台北因為天氣一直變來變去出門都要帶雨傘有夠煩，所以政府決定將盡可能多的捷運路線都停駛，但還是要維持任兩個捷運站可以透過其他捷運站互相連通，因此捷運圖變成了一棵 $N$ 個點的樹。
因為寒假沒事幹，所以喂喂想從某個起點站搭車搭到終點站，並且在中途每個捷運站都下車去吃當地美食，順便熟悉一下新的捷運圖。但有一個問題是喂喂很瘦，肚子裝不下多少食物。已知第 $i$ 個捷運站的食物有 $w_i$ 公斤，而喂喂的肚子只裝的下 $K$ 公斤的食物，所以任何時刻喂喂的肚子都不能裝超過 $K$ 公斤的食物，並且保證 $w_i \leq K$，也就是不會有喂喂吃不下去的食物。不過幸好因為台北很會蓋捷運站，每個捷運站都有廁所，因此喂喂可以在任何捷運站的廁所把肚子裡的食物拉乾淨，就可以再次進食。
現在喂喂想問你 $Q$ 個問題，對於第 $i$ 個問題請回答如果喂喂從第 $s_i$ 站搭到第 $t_i$ 站並吃完中途所有捷運站的美食，他最少只需要去上幾次廁所？
注意起點站有可能等於終點站，這時喂喂還是要吃掉該站的食物。
Input Format
第一行有三個整數 $N,Q,K$，表示捷運站的數量，詢問次數以及喂喂肚子的承重。
第二行有 $N$ 個整數 $w_1,w_2, \cdots ,w_N$ 代表每個捷運站的美食重量。
接下來 $N-1$ 行各有兩個整數 $a_i,b_i$ 代表這兩個捷運站之間有通車。
接下來 $Q$ 行各有兩個整數 $s_i,t_i$ 代表喂喂想知道以這兩個捷運站為起終點的答案。
- $1\leq N,Q\leq 2\times 10^ 5$
- $1\leq K\leq 2\times 10^ {14}$
- $1\leq w_i\leq \min(K,10^ 9)$
- $1\leq a_i,b_i\leq N$
- $1\leq s_i,t_i\leq N$
Output Format
輸出 $Q$ 行，對於第 $i$ 行輸出一個整數代表第 $i$ 個詢問的答案。
Sample Input 1
3 2 3 2 1 3 1 2 1 3 1 2 2 3
Sample Output 1
0 1
Sample Input 2
10 10 10 2 4 5 3 6 1 5 3 2 3 1 2 2 3 2 4 4 5 5 6 6 7 6 8 7 9 9 10 2 1 8 2 4 1 1 9 10 8 2 2 7 6 4 7 1 5 4 10
Sample Output 2
0 1 0 2 1 0 0 1 1 1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0~20 | $N,Q \leq 1000$ | 30 |
| 3 | 0~54 | 無特別限制。 | 70 |