Page **1** of **1**

### 11457 - Classified

Posted: **Tue Jun 24, 2008 10:29 pm**

by **baodog**

I tried constructing RMQ from DFS tree of each node with no parents.

However this TLEs, since there can be O(n) such RMQs.

Is there some way to do it with one RMQ, so each query is O(logn)?

How did you guys solve this one

? Thanks!

### Re: 11457 - Classified

Posted: **Wed Jun 25, 2008 1:01 am**

by **baodog**

maybe construct one RMQ, keep list of indices for each node, and find the closest two nodes by binary search.

### Re: 11457 - Classified

Posted: **Wed Jun 25, 2008 4:18 am**

by **rio**

This problem is about finding LCA in DAG.

I used an algorithm with O(nm) for precalculation and O(1) for query.

-----

Rio

### Re: 11457 - Classified

Posted: **Wed Jun 25, 2008 6:03 am**

by **baodog**

THanks. Do you have a reference? Can you describe your algorithm? Thanks!

### Re: 11457 - Classified

Posted: **Wed Jun 25, 2008 6:29 am**

by **rio**

Search google with "lca dag".

I found paper about it in the first page.

-----

Rio