給定n <= 200000節點和m <= 200000邊的加權無向圖。邊緣權重（整數）可以高達1e9。有q <= 200000查詢。每個查詢給出兩個節點u v和一個整數綁定p (<= 1e9)。如果在u和v之間存在路徑，使得路徑中的每個邊權重爲<= p，則答案爲yes否則爲no。圖論：無向圖中有界邊權的查詢
注意路徑不必最短。只是路徑上的最大重量是<= p。天真的做法當然不起作用。如何快速回答查詢（在O（n lg n）或類似的東西中）？
你描述的問題被稱爲：最寬路徑問題，你可以在這裏找到它：https://en.wikipedia.org/wiki/Widest_path_problem。
可以很容易地證明，每個u，v的最小最大代價u，v之間的路徑等於最小生成樹。因此，您需要找到最小生成樹，以確保您已最小化兩個頂點u，v之間每條路徑的最大代價。
難題在於爲每個查詢決定從u到v的路徑的最大代價是小於還是等於p。
最好的辦法是使用笛卡爾樹（在維基百科中描述的鏈接），這將使你解答在固定時間內每個查詢，我認爲建立笛卡爾樹將是O（nlogn），所以總體O（ nlogn + q）。但是這種方法很難實現。
我覺得你要找的是使用最低公共祖先算法來回答每一個查詢，在你找到最小生成樹後找到最小生成樹（O（E log E））並使用具有一些預處理的最低共同祖先能夠在O（log n）如此全面地O（qlogn + ElogE）中回答每個查詢。最低公共祖先和預處理的一個非常好的方法可以在這裏找到：https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ 上面的文章非常好地描述了所有的解決方案，並提供了足夠的幫助代碼對您的問題有用。
O（mlogm + qlogn）的整體複雜度。 在以下鏈接中可以找到關於重光分解的信息 https://blog.anudeep2011.com/heavy-light-decomposition/