[問題] ancestry problem

[hardcover (精裝版喔)]

給一顆 binary tree，
問某個 node 是不是另一個 node 的 ancestor，
要在 constant time 決定。
允許 O(n) 的 preprocessing。
n: # of node

我做了幾次嚐試都失敗，至少要logn，
3 種 traversal，也看不出什麼線索。

thanks

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.115.235.76
→ hardcover:想到一個，traversal時要對node encoding，不知是不是
→ hardcover:正解
推 ledia:via suffix tree ?
→ ledia:encoding 是否也是 logn 的一種?
→ ledia:啊 我說的 via suffix tree 是找 common ancestor
→ ledia:你的應該是找 lowest common ancestor 的特例?
推 ephesians:反問一個觀念問題,O(n)是constant time?