※ 引述《hardcover (精裝版喔)》之銘言：
: 標題: [問題] ancestry problem
: 時間: Wed Jun 20 14:49:49 2007
:
: 給一顆 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，不知是不是 06/20 15:03
: → hardcover:正解 06/20 15:04
: 推 ledia:via suffix tree ? 06/20 15:39
: → ledia:encoding 是否也是 logn 的一種? 06/20 15:39
對厚 ， 是 logn XD
: → ledia:啊 我說的 via suffix tree 是找 common ancestor 06/20 15:40
: → ledia:你的應該是找 lowest common ancestor 的特例? 06/20 15:40
: 推 ephesians:反問一個觀念問題,O(n)是constant time? 06/20 16:25
是我沒說清 楚 ，
O(n) 是指第一次，此後問你類似的問是你都要在 O(1) 之內回答。
thanks
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.88.92