You are not logged in. Please login at www.codechef.com to post your questions!

×

TALCA - Editorial

8
10

Problem link : contest practice

Difficulty : Medium

Pre-requisites : Lowest Common Ancestor, Trees

Problem : Given a tree, you have to answer the question of the format "r u v" which means which is the LCA of u and v if the root of the tree is at r.

Explanation

At first, let's consider some partial solutions.

How to get 20 points

For this sub-task you an find the LCA in any way you want as long as the complexity is not slower than O(N). For example, by DFS from the root, you can number the vertices so that given two arbitrary vertices, you can check whether they are ancestor and descendant(for this, you can store T_in and T_out for each node. T_in is the time when the DFS for that node was begun. T_out is the time when the DFS was over).

How to get 60 points

Here there are not more than 10 different roots, but the queries are quite high, so you should know the fast way to find LCA. More specifically O(Nlog(N)) is enough. Notice that there will be no more than 10 different roots so your complexity will be O(10 × Nlog(N)).

How to get 100 points

There are two interesting observations that you can make:

  1. Given the query "r u v" what can be the answer? The possible answers are r, u, v, LCA(r, u), LCA(r, v), LCA(u, v) where LCA(x, y) is LCA of x and y when the tree is rooted at 1.

  2. The LCA of u and v when the root is at r is the vertex x such that the sum of shortest path from x to u, x to v and x to r is smallest.

With this two observations you need to implement two function: finding LCA and distance of the two vertices in the tree. Proof for these two observation is not hard but too long to be mentioned here. It is left as an exercise for you.

Solutions : setter tester

This question is marked "community wiki".

asked 27 Jul '14, 14:46

darkshadows's gravatar image

5★darkshadows ♦
3.0k93163187
accept rate: 12%


This might be a much simpler way for unrooted queries: link

link

answered 27 Oct '14, 15:49

sudeepdino008's gravatar image

3★sudeepdino008
10416
accept rate: 0%

@sudeepdino008 did you find the proof why it works?

(30 Nov '17, 23:53) pk3013★

For Query(root,u,v):

Let a=LCA(u,v),b=LCA(root,u) and c=LCA(root,v) and the answer for the query is the one value that is different from other two if all of them are not equal

i.e

if(a==b)return c;
else if(b==c)return a;
else if(c==a)return b;
else throw an error ; // condition no possible

My Solution

link

answered 24 Jul '17, 19:46

abhishek_a's gravatar image

1★abhishek_a
112
accept rate: 0%

Infact, the only possible answers are LCA(r, u), LCA(r, v), LCA(u, v). I proved it by drawing the diagrams corresponding to all possible scenarios for the arrangements of the 3 nodes and the node no. 1.

link

answered 06 Sep '18, 12:58

roll_no_1's gravatar image

6★roll_no_1
413
accept rate: 18%

Can anyone tell me why am i getting TLE for the two test cases?

My sol link: here

Is there any special case that i need to handle. Any suggestion would be appreciated. Thanks

link

answered 26 Sep '15, 23:28

ravi_shank's gravatar image

4★ravi_shank
11
accept rate: 0%

edited 26 Sep '15, 23:30

How do we keep the parent-child relationship for different roots in the 20 points solution?

link

answered 24 Jun '16, 11:44

randomprime's gravatar image

3★randomprime
211
accept rate: 0%

IS THIS A Binary TREE?

OR it can be a tree with any number of children?

link

answered 24 Jul '17, 22:06

dontfindme's gravatar image

0★dontfindme
32
accept rate: 0%

edited 24 Jul '17, 22:07

it can be a tree with any number of children!

(30 Nov '17, 23:45) pk3013★

What is wrong with my solution: What I am doing is : If r is not in subtree of orig_lca then origlca is the answer else { if(lca(u,r)==origlca and lca(v,r)==origlca){ then answer = origlca } if(lca(u,r)==origlca){ then answer = lca(v,r); } if(none of above){ then answer = lca(u,r); } }

https://www.codechef.com/viewsolution/19741297

link
This answer is marked "community wiki".

answered 16 Aug '18, 15:53

vibhor_1's gravatar image

2★vibhor_1
11
accept rate: 0%

edited 16 Aug '18, 15:55

How this works? Can anyone tell the proving of this:

.............................................................................

Let LCA(u, v, w) be the LCA of v and w with respect to root u. To compute LCA(u, v, w), we can compute, for any fixed r,

LCA(r, u, v)

LCA(r, u, w)

LCA(r, v, w)

and take the "odd man out", i.e., if two are equal and the third is different, then take the third, else they're all equal, so take that node.

link

answered 25 Oct '18, 23:27

jvjplus's gravatar image

2★jvjplus
815
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,237
×699
×242
×12

question asked: 27 Jul '14, 14:46

question was seen: 7,557 times

last updated: 25 Oct '18, 23:27