樹樹樹樹樹
題目：
給定N-1條邊，為一棵N個節點的樹，並進行若干操作，如下：
- CHANGE i ti: 改變第i條邊的權重為ti
- QUERY a b: 詢問從a走到b的過程中，權重最大的那條邊之權重。
做法：
對樹做樹鏈剖分(輕重鏈剖分)，並將鏈上的點依序編號，一條鏈找到底再找另一條。
於是同一條鏈上的點編號是連續的，可以壓到線段樹上作區間最大值的查詢。
且由於每一個節點(除了ROOT)皆只有一個父節點，故每個節點存放自己到父節點間的邊權。
每次QUERY a b，找a, b的LCA，一邊爬一邊更新最大值。
code:
沒有留言:
張貼留言