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

مسائلی که در آن ها تعدادی پرسش مطرح می شوند دو نوع راه حل دارند. راه برخط
(online)
و راه برون‌خط
(offline).
در راه برخط شما مجبورید هر سوال را در لحظه پاسخ دهید و تا به پرسش فعلی پاسخ
ندهید نمی‌توانید پرسش بعدی را دریافت کنید. اما در راه برون خط می توانید همه پرسش ها
را دریافت کرده و سپس شروع به پاسخ دادن کنید.

در این بخش با یک راه برون خط برای مسائلی که مطرح شد ارائه می‌کنیم. چون برخط بودن یک
محدودیت است، راه های برون خط پیچیدگی کمتری دارند.

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

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

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