如何回答DAG上最長體重路徑上的單節點編輯查詢

Question

在形式上，我們給出了一個圖G，其中'n'個節點上都有+ ve個數字。我們被賦予了沒有循環的有向邊。那麼我們被要求回答Q查詢，每個查詢要求編輯G上的節點權重，並且我們必須打印最長權重路徑權重。請注意，每個查詢意味着從原始圖形編輯單個節點。 N < = 10^5 & Q < = 10^6。什麼是最具時間效益的解決方案？

Ofcourse bruteforce將採取太多的O（n q）。我嘗試了2,3種不同的bruteforce，它可以提供更好的平均時間複雜度，但是我可以找到每個解決方案的至少一個測試數據，如果我們反覆詢問就像O（n q）一樣差。

Answer 1

要回答每個O（1）次的查詢，只需知道每個節點使用/不使用該節點的最重路徑的權重，因爲這些類中的路徑權重會受到影響通過改變節點的重量。通過例如爲每個節點計算該節點是源/匯的最重路徑的權重，在O（n）時間中直接實現「使用」一半。

「不使用」的一半是什麼使這個問題變得有趣。假設節點按照拓撲順序編號爲1..n，弧從低到高。使用之前計算的數據，我們可以給定一個弧u→v，在O（1）中計算包含該弧的最重路徑的權重。這樣的路徑肯定會跳過節點u + 1..v-1，因此我們可以相應地更新這些節點的「不使用」最大值。如果我們對所有弧進行此操作，包括一些來自哨兵源0（權重爲0到1..n）的哨兵弧到砝碼爲0的哨兵宿n + 1，則我們得到正確的「不使用」值。

現在，以明顯的方式做這件事太慢了：O（mn）預處理的時間總共爲O（mn + q），其中m是弧的數量，n是節點的數量，q是查詢的數量。分段樹將預處理時間縮短爲O（m log n）。