الگوریتم برون‌خط تارجان¶

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

این مساله ساده است. کافیست همه پرسش ها را دریافت کرده و سپس از ریشه درخت DFS بزنیم. هنگامی که وارد یک راس شدیم، آن را در یک وکتور پوش می‌کنیم و هنگام خارج شدن آن را پاپ می‌کنیم. به این ترتیب هنگامی که در یک راس هستیم، خودش و تمام اجدادش درون وکتور هستند و به ترتیب ارتفاع چیده شده‌اند. پس هنگامی که به یک راس رسیدیم می‌توانیم تمامی پرسش های مربوط به آن را از \(O(1)\) پاسخ دهیم. به این ترتیب راهی خطی در اختیار داریم.

راه مساله LCA¶

ابتدا تمام پرسش ها را دریافت می کنیم و برای هر راس، لیستی از پرسش های مربوط به آن را تهیه می کنیم. این کار در زمان خطی نسبت به ورودی قابل انجام است.

سپس روی درخت DFS می‌زنیم. هنگامی که به یک راس می رسیم، یک دسته ایجاد می کنیم و این راس را درون آن می‌گذاریم. و هنگامی که از این راس خارج می شویم، دسته ای که این راس درون آن است را با دسته پدر این راس ترکیب می‌کنیم. به این ترتیب اگر روی یک راس مانند u باشیم، هر راس دیگر مانند v در دسته‌ای قرار دارد که سر دسته آن، جد مشترک بین آن دو است. عملیات های ترکیب را می‌توان با DSU انجام داد و بنابراین پیچیدگی این الگوریتم برابر است با: \(O((n+q)*a(n))\) که در آن \(a(n)\) همان تابع معکوس آکرمان است.