作者LinkCar (Link)
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Wed Jun 20 20:16:59 2007
※ 引述《hardcover (精装版喔)》之铭言：
: 给一颗 binary tree，
: 问某个 node 是不是另一个 node 的 ancestor，
: 要在 constant time 决定。
: 允许 O(n) 的 preprocessing。
: n: # of node
: 我做了几次嚐试都失败，至少要logn，
: 3 种 traversal，也看不出什麽线索。
: thanks
这题应该是转换成 +-1RQM 的问题。
就可以在O(n) preprocessing结束。
然後O(1)的询问
转成RMQ要先做EULER TRAVERSAL
路径所经过的节点的，把该节点的LEVEL依序存在一个阵列里。
询问两节点间的最小LEVEL(在阵列内RANGE MIN QUERY)
又TREE里面节点跟节点之间高度只差一，所以阵列里面两两相邻差一。
因此叫做+-1RMQ
....
....
但是RMQ怎麽以O(n)preprocess
我以前有看过文章....但是文章找不到了，他的方法我也没学起来@@
我找到文章再丢连结，我一时找不到我那时候看的文章
抱歉，看到同样问题分享一下我的经验，虽然还没解决问题= =
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.15.240
1F：推 ledia:应该是 RMQ ? (Range Min Query) 据我所知, RMQ 会 reduct 06/20 20:34
3F：→ LinkCar:对= =是RMQ 对不起我错了 06/20 20:37
4F：→ ledia:到 lowest common ancestor 06/20 20:35
5F：→ LinkCar:其实是我题目看错了....对不起 06/20 20:38
6F：→ ledia:或是有更好的做法? 06/20 20:38
7F：→ LinkCar:这样应该可以用..就判对LCA是不是询问的两个节点之一 06/20 20:42
8F：→ LinkCar:这是广用解法，单问A是不是B的祖先应该有很简单的方法 06/20 20:43
※ 编辑: LinkCar 来自: 61.230.15.240 (06/20 20:46)
9F：推 ledia:wow, 看起来 +-1 RMQ 简单好用, 我觉得够好了 XD 06/20 20:52
10F：→ hardcover:感恩哩 06/21 00:31