مسأله‌ی دوم

نشان دهید در صورتی که علی، تا زمانی که مجبور نباشد، دنباله‌ی تکراری تولید نکند، هر نحوه‌ی انجام عملیات به تعداد یکسانی بار انجام عمل می‌انجامد.

برای اثبات گزاره‌ی راهنمایی فوق، گرافی در نظر گیرید که هر راس آن، یکی از دنباله‌های ممکن قابل ساخت باشد. از دنباله‌ی $A$ به دنباله‌ی $B$ یال جهت‌دار قرار می‌دهیم اگر بتوان از دنباله‌ی $A$، در یک عمل، دنباله‌ی $B$ را تولید کرد.

راس‌های دنباله‌هایی که علی در حال حاضر نوشته را در گراف فوق قرمز کنید. هر عمل، معادل قرمز کردن راسی جدید از روی یکی از رئوسی است که به آن یال خروجی دارد.

تمام دنباله‌‌های به صورت $\{v\}$ را در نظر بگیرید. بر طبق راهنمایی‌های بالا، می‌توانیم هر یک را در نظر گرفته، تا زمانی که می‌توان دنباله‌ی جدیدی از روی آنچه داریم به دست آورد، روی دنباله‌ی فعلی عملیات انجام دهیم. برای مثال، اول روی $\{v\}$ عملیاتی انجام می‌دهیم تا دنباله‌ی $A$ بدست آید. سپس، با انجام عمل روی دنباله‌ی $A$، دنباله‌ی $B$ را می‌سازیم. سپس با انجام عمل روی $B$… و در نهایت، می‌ایستیم.

فرض کنید $v$ فرزندی مثل $u$ داشته که برای هر فرزند دیگری از $v$ مثل $x$ داشته باشیم $size_x < size_u$

در حالت فوق، پس از انجام اعمال، به دنباله‌ی $\{u\}$ می‌رسیم. پس از چند عمل این اتفاق می‌افتد؟

هر راس زیردرخت $v$ به غیر از رئوس زیردرخت $u$ دقیقا یک بار از دنباله حذف می‌شود.

تعداد کل اعمال، برابر با جمع تعداد رئوس تمام زیردرخت‌ها، غیر از زیردرخت بزرگ‌ترین فرزندشان خواهد بود. چنین تحلیل اردری را کجا دیده‌اید؟

اگر دقت کنید، ایده‌ی تحلیل اردر در DSU دقیقا به همین نحو است. تعداد رئوس زیردرخت فرزند بزرگ را جمع نمی‌زنیم و باقی زیردرخت‌ها جمع زده می‌شوند.

اگر بین فرزندان راس $v$، راسی به طور یکتا بیشترین $size$ را نداشت چه؟

در دنباله‌ی مرتب شده‌ی اولیه، میان تمام فرزندان با بیشترین تعداد راس در زیردرخت، چپ‌ترین را در نظر بگیرید.