[問題] dynamic tree, query path

[flere (人間失格)]

標題不知道下的好不好..> <

問題:
一棵N個點的tree
接下來有許多操作, 操作共有兩種:
    1. 把一個無色的點上色, 或是把一個上色的點變成無色
    2. 給一個點v, 輸出v到root路徑裡所有上色的點編號


請問有相關的paper或是關鍵字嗎?
還是已經有某個資料結構支援這個問題了??


謝謝大家!!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.236.49.74
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1415267062.A.B5C.html
※ 編輯: flere (119.236.49.74), 11/06/2014 17:44:38
→ yr: 看起來 DFS 就可以做到，有其他限制嗎？
DFS?
沒有特別處理對於操作二的話
最差會到O(N)喔!
※ 編輯: flere (119.236.49.74), 11/06/2014 18:53:57
→ yr: 2? 所以是 binary tree ? 除非你這樹有什麼特性，不然
→ yr: 一般最差就是 O(n) ，題目並沒有提到任何特性啊
呃我就是想問看看能不能對樹進行改造讓兩個操作都能很快..
比如說樹鏈剖分, 對每條鏈套其他資料結構..
※ 編輯: flere (119.236.49.74), 11/06/2014 19:04:46
→ yr: 加一個到 parent 的指標，然後用 hash table 存每個點？
推 fenzhang: 樹鍊剖分套BIT套SET
→ ferng1021: (2) 要輸出每一個點的編號就 O(n) 了
推 singlovesong: 但是也許可以amortized
大部分我們在估複雜度的時候
會把輸出的部分變成occurence來看
所以可以變成O(logn + occ)之類的沒有問題~
※ 編輯: flere (119.236.49.74), 11/06/2014 21:49:56
推 paae0226: 是 kerker 耶  所以這是要 online?
→ yr: (2) 最差就 O(h) ，而 O(h) 最差是 O(n)
→ yr: 如果樹可以改成 self-balancing binary tree 才能 O(logn)
推 paae0226: 想了一下還是推 5 樓 f 大 不過好像有 3 個 log 就是
推 esrever: splay tree 似乎可以做到 amortized O(logn)
→ esrever: 欸不對  不能用 splay tree，它會改變樹形...
推 DJWS: 問這些人 http://ppt.cc/ZSvz 不過我估計台灣沒人能回答你
推 stimim: link-cut tree, heavy-light decomposition 應該都可以用
→ stimim: 如果要輸出編號而不是數量的話，那一定會到 O(n) 不是嗎？
→ stimim: 假如把所有的點都上色，每次都query最遠的那個點
把上面的想法拿掉好了XD
總之用tree decomposition必定能解

很多算法的複雜度估算都會使用output sensitive
也就是我的複雜度除了output的時間外希望能越快越好
比如說O(logn+occurence)

這樣即使occurence是0也只會花到最多O(logn)
但如果是直接走回root看結果的話
就必定O(n)了
※ 編輯: flere (119.236.49.74), 11/07/2014 20:29:37
推 fenzhang: 離線做可以把所有點存在的時間區間弄出來，之後邊DFS邊
→ fenzhang: 維護線段數套SET可以做到修改均攤lg^2查詢均攤lg+occ