11354 - Bond

[sclo]

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]

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]

I think that works, but I haven't solved that problem yet.

[Adrian Kuegel]

If you use union by rank, you can answer queries in O(log n) on the union find tree.

[shanto86]

can you please describe it a bit more?

[sclo]

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]

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]

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]

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]

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]

Can anyone tell me the algo for LCA...i am not getting it...

[Jan]

You can check the following link

http://www.topcoder.com/tc?module=Stati ... onAncestor

[aman181993]

(http://www.spoj.pl/problems/QTREE/)

can some1 please explain the updation part in this problem using LCA

[csprajeeth]

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