سوال ۱

خیکوله و خیکولا با هم بازی زیر را انجام می‌دهند:

• ‎ بازی آن‌ها به صورت نوبتی روی یک درخت انجام می‌شود که تعدادی مهره روی رئوس آن قرار دارد. (ممکن است روی یک راس چند مهره باشد.)
• ‎ تعداد مهره‌ها زوج است.
• هرکس در نوبت خودش دو مهره‌ی دلخواه را که فاصله‌شان حداقل دو یال می‌باشد انتخاب می‌کند و هر کدام را به اندازه‌ی یک یال به دیگری نزدیک می‌کند. یعنی فاصله دو مهره دقیقا به اندازه‌ی دو یال کاهش می‌یابد.
• بازی وقتی تمام می‌شود که دیگر حرکتی با مهره‌ها قابل انجام نباشد. در این صورت حتما همه‌ی مهره‌ها یا روی یک راس قرار دارند، یا روی دو راس مجاور. در حالت اول برنده‌ی بازی خیکوله است. در حالت دوم، درصورتی که روی هر یک از دو راس زوج تا مهره قرار داشه باشد، خیکوله برنده‌ی بازی است و در صورتی که رو هر دو راس فردتا مهره قرار داشته باشد، خیکولا می‌برد. (توجه کنید که تعداد مهره‌ها زوج است.)
• ‎‎ خیکوله اولین حرکت را انجام می‌دهد.

با فرض اینکه درخت دارای ‎$n$‎ راس و ‎$k$‎ مهره است، الگوریتمی از ‎$O(n‎ + ‎k)$‎ ارائه دهید که با گرفتن اطلاعات درخت و مهره‌ها، برنده‌ی بازی را مشخص کند.

• سوال بعد