11354  Bond
Moderator: Board moderators
11354  Bond
Looking at the problem, I think the solution can be found by kruskal's algorithm. The problem is how to answer the queries fast enough? In the worst case, the tree can be linear, each query takes O(n) time.
I've not coded it yet.
Hi, I've have not coded it yet but what I thought was the following.
First compute the min spanning tree.
Apply an algorithm similar to LCA to the tree as in problem QTREE of http://www.spoj.pl. (http://www.spoj.pl/problems/QTREE/)
First compute the min spanning tree.
Apply an algorithm similar to LCA to the tree as in problem QTREE of http://www.spoj.pl. (http://www.spoj.pl/problems/QTREE/)

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Code: Select all
I would like to know how the query can be answered directly on the union find datastructure.
I solved it just using LCA and calculated maximum edge cost from each vertex by 2^j vertices up.
Then each querry also can be answered in O(log n). Answer is the maximum value from LCA to vertex1 or from LCA to vertex 2.
When constructing the unionfind tree, add weight info to the edge in the unionfind tree.
For query(a,b):
LCA(a,b) is LCA of a,b in unionfind tree.
The hight of tree is O(logn), so you could answer the query with O(logn).

Rio
For query(a,b):
Code: Select all
query(a,b) := max(the last edge weight of path a > LCA(a,b),
the last edge weight of path b > LCA(a,b));
The hight of tree is O(logn), so you could answer the query with O(logn).

Rio
Re: 11354  Bond
I really want to know what your algorithm is. I know I can use a segment tree or something like this, but I really don't know HOW to use it.
I'm interested in your O(log N) solution, so can you explain it more carefully, or do you have any lecture about it?
I'm interested in your O(log N) solution, so can you explain it more carefully, or do you have any lecture about it?
Re: 11354  Bond
Unionfind tree is different from segment tree.davidsun wrote:I really want to know what your algorithm is. I know I can use a segment tree or something like this, but I really don't know HOW to use it.
I'm interested in your O(log N) solution, so can you explain it more carefully, or do you have any lecture about it?
Heres a pdf about unionfind tree I found on web:
http://valis.cs.uiuc.edu/~sariel/teach/ ... /22_uf.pdf
Once you understand about this data structure, I think you could understand the algorithm I said.

Rio
Re: 11354  Bond
Can anyone tell me the algo for LCA...i am not getting it...
"Accepted" is my passion but RTE is my weakness.....
Re: 11354  Bond
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 1
 Joined: Fri Mar 29, 2013 10:59 pm
Re: 11354  Bond
(http://www.spoj.pl/problems/QTREE/)
can some1 please explain the updation part in this problem using LCA
can some1 please explain the updation part in this problem using LCA

 New poster
 Posts: 5
 Joined: Sat May 26, 2012 7:25 pm
Re:
Brilliant. I never thought of that. I constructed a new tree and answered LCA(u,v) using heavylight decomposition technique... Got me the last rank... and then used ur idea... rank 19. thanksrio wrote:When constructing the unionfind tree, add weight info to the edge in the unionfind tree.
For query(a,b):LCA(a,b) is LCA of a,b in unionfind tree.Code: Select all
query(a,b) := max(the last edge weight of path a > LCA(a,b), the last edge weight of path b > LCA(a,b));
The hight of tree is O(logn), so you could answer the query with O(logn).

Rio