One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.
This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.
Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.
The places are designated by consecutive integers from 1 to $N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $N$ places.
The first line contains the total number of test cases that follow.
Each test case begins with a line that first holds the number $N$ of places ( $1 \le N \le 3000$ ) followed by the number $R$ of roads ( $1 \le R \le 100000$ ). Then there are $R$ lines with three integers each ($a$ , $b$ , and $l$ ), each of which defines a road connecting the places $a$ and $b$ ( $1 \le a, b \le N$ ) with length $l$ ( $1 \le l \le 1000000$ ).
Thereafter, each test case continues with the number $Q$ of queries on a line by itself ( $1 \le Q \le 1000$ ). Each of the next $Q$ lines holds two integers $k$ and $t$ , indicating a query by a knight who lives at place $k$ and needs to go to a tournament at place $t$ ( $1 \le k, t \le N$ , $k \neq t$ ).
For each test case output a line containing the word ``Case’’, a single space, and its serial number (starting with $1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.
由於詢問兩個點之間的路徑上的最小值最大邊，不外乎地可以先做一次最小成本樹，根據定義，拆分成 s - t 集合，最小成本樹的邊一定是 s - t 之間的最小邊。
那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。
因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。
在同一水平下，還是需要知道 LCA 的所在高度，否則也可以水平線不斷地一步一步往上提，雖然最慘也許是 O(n) 但是經由之前的調整已經很加速很多。
本來應該套用 LCA Tarjan 的作法來加速，但是還沒有做到這樣的地步速度就很快。如果詢問次數再多一點就必須做到這一步。