樹樹樹哦
連結：SPOJ QTREE3 - Query on the tree again!
題目：
給定一棵N個節點的樹，節點上有黑色或白色兩種，一開始全都是白的
然後有Q次操作，如下：
- 0 i: 把i點的顏色反轉，即黑變白或白變黑
- 1 v: 輸出從1號點走到v點的路徑中遇到的第一個黑點的編號，若無則答案為-1
做法：
每次詢問都是從1走到v，用樹鏈剖分+線段樹維護
在剖分的時候有在點上留下邊的時間戳
要找1 ~ v路徑中離1最近的，就在樹上維護區間中黑點最小時間戳，若都沒有黑點則INF
查詢時像做LCA一樣從v爬上去並更新答案
不太會算剖分的複雜度，但應小於O(Q(logN)^2)(?)
code:
沒有留言:
張貼留言