AminAnvari's blog

LCA problems
By AminAnvari, 10 years ago, In English

Hi :)
These are some LCA (lowest common ancestor) problems. I hope you enjoy them.
I tried to sort them by difficulty. If you know more problems, add it to comments.

208E - Blood Cousins
191C - Fools and Roads
519E - A and B and Lecture Rooms
587C - Duff in the Army
609E - Minimum spanning tree for each edge
178B3 - Greedy Merchants
176E - Archaeology
466E - Information Graph

  • Vote: I like it
  • +94
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Hello, A Secret Mission — LOJ , Min Max Roads — LOJ , LCA — SPOJ , Kth Ancestor — HackerRank

Here I found a few LCA / LCA modifications :)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Thank you so much for taking the time to compile all these lists.

I really appreciate your work!

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

504E - Misha and LCP on Tree

LCA + hash

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Thanks for gathering all problems with same tag!! I was looking for LCA ones :D

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Another LCA problmes:

Qtree spoj : LCA + Heavy-light Decomposition + segment tree

372D - Choosing Subtree is Fun : LCA + sorting + dfs(starting time calculating) + two_pointer (or Heavy-light Decomposition)

342E - Xenia and Tree : LCA + Sqrt Decomposition

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

629E - Famil Door and Roads

→ Reply
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

A great LCA problem from codechef : TOMJERGA

→ Reply
»
8 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

916E - Jamie and Tree

the newest one :)

→ Reply
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

I wrote code for 191C but I got verdict: wrong answer on test 3. please, tell to me, why my code does not works correctly. link: https://mirror.codeforces.com/contest/191/submission/39604271

→ Reply
»
8 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

986E - Prince's Problem

Nice problem :)

→ Reply
»
8 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

http://www.spoj.com/problems/DISQUERY/ this is problem based only on LCA. this problem is from the SPOJ. update: this problem is not based only on lca, sorry for mistake.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1062/problem/E Nice LCA problem ^_^

→ Reply
»
7 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

https://www.hackerrank.com/contests/101hack26/challenges/sherlock-and-queries-on-the-graph (LCA + Bridge finding) :) and thank you so much for your list

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Two easy ones and a harder one

Kattis — tourists Kattis — boxes Kattis — pokegene

→ Reply
»
6 years ago, hide # |
 
Vote: I like it -22 Vote: I do not like it

Thanks for these problem list and i was waited for this

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

this problem from a recent round

1-Trees and Queries

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

https://mirror.codeforces.com/contest/1328/problem/E

in the recently contest

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

csacademy's Identifying-Infected is a LCA tagged problem. How to approach this? Sorry for necro-bumping.

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Answer is the number of cut vertices on the simple path between query vertices in the Block-Cut Tree of the graph. This can be found in logN time by calculating the LCA of the Block-Cut Tree.

    → Reply
»
4 years ago, hide # |
← Rev. 4  
Vote: I like it +5 Vote: I do not like it

LCA problem from the contest just now codeforces.com/contest/1702/problem/G2

→ Reply
»
4 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Highly recommend))) 786D - Rap God

→ Reply
»
3 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/gym/101630/problem/L problem L is very nice problem that recquires LCA to implement the main idea it asks for.

→ Reply