در این قسمت 3 سوال وجود دارد
یک درخت ریشه دار و وزن دار n راسی داریم. q پرسش از ما پرسیده می‌شود. هر پرسش از ما می‌پرسد که جمع وزن یال های مسیر بین دو راس ورودی چند است. اگر برای مساله پایین ترین جد مشترک راهی از مرتبه زمانی $O(f(n,q))$ داشته باشیم، الگوریتمی از همین مرتبه ارائه دهید که به پرسش ها پاسخ دهد. اگر به جای جمع وزن یال‌ها، xor وزنشان مطلوب بود، می‌توانستید مساله را با $O(n+q)$ حل کنید؟
فرض کنید برای مساله‌ها راهی از مرتبه زمانی $O(f(n,q))$ داریم، یک درخت ریشه دار و وزن دار n راسی داریم. q پرسش از ما پرسیده می‌شود. در هر پرسش دو راس به ما داده می شود و راس k ام در مسیر بین این دو خواسته می‌شود. الگوریتمی از $O(f(n,q))$ ارائه کنید.
به یک زیرمجموعه از رئوس درخت، یک درخت مجازی می گوییم، اگر LCA هر دو عضوی از این مجموعه، خود عضو این مجموعه باشد. حال برای هر مجموعه A ثابت کنید درخت مجازی ای شامل رئوس این مجموعه وجود دارد که اندازه آن حداکثر دو برابر اندازه مجموعه A است.