[2020多校A層12.1]樹

求解樹上從u到v的最長貪心上升序列，也就是只要有比它大的就選擇它，可以發現這個問題性質，就是每個點對應了唯一的一個第一個比它大的點，那么我們可以向它們之間連邊，然后問題就轉化為求解從當前點上面的鏈中第一個大于c的位置和第一個深度小于dep[v]的位置。然后樹上倍增維護即可。

另外我們也可以用單調棧直接處理，將詢問離線，然后維護當前點向根這條鏈的單調棧，然后二分對應位置即可。然后對于回溯需要存儲下來彈掉的元素，然后回溯時要加回去。

總結

以上是生活随笔為你收集整理的[2020多校A层12.1]树（倍增/单调栈/dfs栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。