====== زیردرخت مینیمال (Minimal Subtree) ====== یک درخت $n$ راسی داریم که راس‌های آن با $1$ تا $n$ شماره‌گذاری شده‌اند. به شما $q$ کوئری داده می شود. در هر کوئری دو عدد $l$ و $r$ به شما ورودی داده می‌شود و شما باید اندازه کوچکترین زیرمجموعه همبند از رئوس درخت که شامل تمام رئوس $l$ تا $r$ هستند را خروجی دهید. ===== ورودی ===== در خط اول ورودی $n$ و سپس $q$ می‌آید. در هر یک از $n-1$ خط بعدی دو عدد $v_i$ و $u_i$ می‌آید که نمایانگر یال‌های درخت است. در $i$ امین خط از $q$ خط بعدی دو عدد $l_i$ و $r_i$ می‌آید که نمایانگر کوئری $i$ ام است. ===== خروجی ===== در $i$ امین خط از خروجی پاسخ کوئری $i$ ام را خروجی دهید. ===== زیرمسئله‌ها ===== * زیرمسئله اول (۷ نمره): $n, q \leq 2\,000$ * زیرمسئله دوم (۸ نمره): درخت ورودی مسیر است. * زیرمسئله سوم (۱۲ نمره): $n, q \leq 100\,000, r_i - l_i \leq 100$ * زیرمسئله چهارم (۱۸ نمره): $n, q \leq 50\,000$ * زیرمسئله پنجم (۵۵ نمره): بدون محدودیت اضافی ===== محدودیت‌ها ===== * محدودیت زمان: ۶ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت * $n \leq 250\,000$ * $q \leq 1\,000\,000$ * $1 \leq v_i, u_i \leq n$ * $1 \leq l_i \leq r_i \leq n$ ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |5 3 \\ 1 2 \\ 1 3 \\ 2 4 \\ 2 5 \\ 3 5 \\ 1 4 \\ 1 3|5 \\ 4 \\ 3| |7 10 \\ 6 5 \\ 3 6 \\ 7 4 \\ 4 5 \\ 1 6 \\ 4 2 \\ 1 5 \\ 3 6 \\ 4 5 \\ 1 6 \\ 2 3 \\ 4 4 \\ 2 6 \\ 2 2 \\ 1 6 \\ 2 5|6 \\ 4 \\ 2 \\ 6 \\ 5 \\ 1 \\ 5 \\ 1 \\ 6 \\ 5| * [[سوال ۱|سوال قبل]] * [[سوال ۳|سوال بعد]]