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

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

Here I found a few LCA / LCA modifications :)

Some basic LCA problems? Which can be solved by only using LCA? By some I mean many please! O_o

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

I really appreciate your work!

504E - Misha and LCP on Tree

LCA + hash

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

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

342E — Xenia and Tree can be solved by both -decomposition and centroid decomposition.

-decomposition solution

Centroid decomposition solution

629E - Famil Door and Roads

A great LCA problem from codechef : TOMJERGA

916E - Jamie and Tree

the newest one :)

Nice problem

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://codeforces.com/contest/191/submission/39604271

986E - Prince's Problem

Nice problem :)

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.

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

But Why I am getting WA :(

My CODE

DFS + LCA + Dual Segment Tree...

Solved in O(n*log(n)^2)

Longest Code in my life but what a nice problem!!!

Marathon on a Tree Simple application of LCA

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

Two easy ones and a harder one

Kattis — tourists Kattis — boxes Kattis — pokegene

Thanks for these problem list and i was waited for this

this problem from a recent round

1-Trees and Queries

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

in the recently contest

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

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`

.would you plz provide a link about block-cut tree.