شرح مساله
============

در این فصل با یک درخت ریشه دار سر و کار داریم و دو مساله زیر را روی این درخت بررسی می‌کنیم.

مساله جد در ارتفاع خاص
----------------------

در این مساله یک درخت ریشه دار
n
راسی ورودی داده می‌شود و سپس
q
پرسش از ما انجام می‌شود. در هر پرسش یک راس مانند v و یک عدد مانند
h
داده می‌شود. تضمین می‌شود که ارتفاع راس از
h
بیشتر است و از ما جد راس
v
که در ارتفاع
h
قرار دارد
(و یکتاست)
از ما خواسته می‌شود.

مساله پایین ترین جد مشترک
-------------------------

در این مساله یک درخت ریشه دار
n
راسی ورودی داده می‌شود و سپس
q
پرسش از ما انجام می‌شود. در هر پرسش دو راس مانند
v و u
به ما داده می‌شود و از ما پایین ترین جد مشترک
این دو راس خواسته می‌شود.
به پایین ترین جد مشترک دو راس عموما
LCA
می گویند که مخفف
Lowest Common Ansector
است.

ارتباط این دو مساله
--------------------

اگر برای مساله اول یک راه حل داشته باشیم که هر پرسش را از
:math:`O(x)`
پاسخ دهد، می‌توانیم هر پرسش از مساله دوم را با
:math:`O(x*lg(n))`
پاسخ دهیم.

LCA
این دو راس را در نظر بگیرید. جدهایی که از ارتفاع آن راس
بالاتر هستند مشترک هستند و جدهای پایین‌تر متفاوت هستند. پس می‌توانیم
روی ارتفاع باینری سرچ بزنیم. برای این که چک کنیم جد ارتفاع x این دو راس
مشترک است یا خیر کافیست که جد ارتفاع
x
هر دو راس را به کمک راه اول به دست آوریم و مقایسه کنیم که آیا یکی هستند یا خیر.