شرح مساله¶

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

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

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

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

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

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

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