標題不知道下的好不好..> <
問題:
一棵N個點的tree
接下來有許多操作, 操作共有兩種:
1. 把一個無色的點上色, 或是把一個上色的點變成無色
2. 給一個點v, 輸出v到root路徑裡所有上色的點編號
請問有相關的paper或是關鍵字嗎?
還是已經有某個資料結構支援這個問題了??
謝謝大家!!

看起來 DFS 就可以做到，有其他限制嗎？2? 所以是 binary tree ? 除非你這樹有什麼特性，不然一般最差就是 O(n) ，題目並沒有提到任何特性啊加一個到 parent 的指標，然後用 hash table 存每個點？

樹鍊剖分套BIT套SET

(2) 要輸出每一個點的編號就 O(n) 了

但是也許可以amortized

是 kerker 耶 所以這是要 online?

(2) 最差就 O(h) ，而 O(h) 最差是 O(n)如果樹可以改成 self-balancing binary tree 才能 O(logn)

想了一下還是推 5 樓 f 大 不過好像有 3 個 log 就是

splay tree 似乎可以做到 amortized O(logn)欸不對 不能用 splay tree，它會改變樹形...

問這些人 http://ppt.cc/ZSvz 不過我估計台灣沒人能回答你

link-cut tree, heavy-light decomposition 應該都可以用如果要輸出編號而不是數量的話，那一定會到 O(n) 不是嗎？假如把所有的點都上色，每次都query最遠的那個點

離線做可以把所有點存在的時間區間弄出來，之後邊DFS邊維護線段數套SET可以做到修改均攤lg^2查詢均攤lg+occ