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 union-find tree, add weight info to the edge in the union-find tree.
For query(a,b):
LCA(a,b) is LCA of a,b in union-find 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
Union-find 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 union-find 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 heavy-light decomposition technique... Got me the last rank... and then used ur idea... rank 19.rio wrote:When constructing the union-find tree, add weight info to the edge in the union-find tree.
For query(a,b):LCA(a,b) is LCA of a,b in union-find 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
![:D](./images/smilies/icon_biggrin.gif)