P3714 [BJOI2017]樹的難題

求解樹上長度在L到R的樹鏈中顏色段權(quán)值和最大的鏈。

首先求解樹上鏈的問題，而且限制了鏈的長度，那么我們需要點分治處理，然后考慮每次分治，我們可以把鏈分成兩類，先處理同色連通塊，再處理異色連通塊，然后采用每次查詢一個子樹的答案然后加入這個子樹的方法。然后對于一個給定鏈，對應(yīng)了一個區(qū)間的權(quán)值，所以我們直接使用線段樹即可，然后合并的時候直接線段樹合并即可。

但是這個問題還有一個特殊性質(zhì)，就是我們每次查詢的區(qū)間長度是一定的，所以如果詢問有序，就可以使用單調(diào)隊列處理了，那么我們可以通過bfs得到一個有序的序列，然后到單調(diào)隊列上跑即可，但是考慮這個復(fù)雜度等于單調(diào)隊列長度，而單調(diào)隊列的長度等于之前出現(xiàn)的最深的點的深度，如果直接跑可能是O(n)的，但是如果我們將深度從小到大排序，那么復(fù)雜度一定是小于當(dāng)前子樹大小的，那么總復(fù)雜度就是O(nlogn)的，然后合并兩個序列我們可以使用歸并，復(fù)雜度也是正確的。

另外我們考慮異色連通塊，需要按照最大深度從小到大處理，這樣可以保證每次復(fù)雜度也是正確的，但是這樣就要要求將整個顏色一起處理。

每一次復(fù)雜度是$O(dlogd+size)$，那么總復(fù)雜度就是$O(nlogn)$

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P3714 [BJOI2017]树的难题（点分治/线段树/单调队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。