## 11354 - Bond

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

### 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.

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

### 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/)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I think that works, but I haven't solved that problem yet.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
If you use union by rank, you can answer queries in O(log n) on the union find tree.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
can you please describe it a bit more?
Self judging is the best judging!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I would like to know how the query can be answered directly on the union find datastructure. I solved it by using the dividing the tree into sqrt(height) layers, and precompute the maximum edge weight to previous layer.

Lomir
New poster
Posts: 19
Joined: Mon Sep 17, 2007 10:05 pm
Contact:

Code: Select all

``I would like to know how the query can be answered directly on the union find datastructure.``
It is interesting to me too.

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.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
When constructing the union-find tree, add weight info to the edge in the union-find tree.
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));
``````
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

davidsun
New poster
Posts: 5
Joined: Fri Apr 11, 2008 3:08 pm

### 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?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11354 - Bond

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?
Union-find tree is different from segment tree.
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

empo
New poster
Posts: 19
Joined: Mon Jul 28, 2008 7:00 pm
Location: India

### 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.....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11354 - Bond

Ami ekhono shopno dekhi...
HomePage

aman181993
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

csprajeeth
New poster
Posts: 5
Joined: Sat May 26, 2012 7:25 pm

### Re:

rio wrote:When constructing the union-find tree, add weight info to the edge in the union-find tree.
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));
``````
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
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. thanks