المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۳:سوال ۲

Slap Game

سعید و فرتاش مشغول انجام یک بازی بر روی یک درخت ‎$n$‎ راسی هستند. در این درخت هر راس ‎$v$‎ دارای یک عدد نامنفی ‎$s_v$‎ است. در ابتدا هر کدام از این دو نفر دارای یک عدد هستند که برابر با $0$‎ است. فرض کنید عدد سعید برابر با ‎$x_s$‎ و عدد فرتاش برابر با ‎$x_f$‎ باشد.

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

شما باید برنامه ای بنویسید که با دریافت اطلاعات مربوط به درخت به دست بیاورد با فرض این که دو بازی‌کن بهترین بازی خود را انجام می‌دهند نتیجه بازی به چه صورت خواهد بود.‎

ورودی

  • در سطر اول ورودی عدد ‎$n$‎ نشان دهنده تعداد رأس‌ها آمده است.
  • در سطر بعدی ‎$n$‎ عدد آمده است که به ترتیب ‎$s_1$‎ تا ‎$s_n$‎ را مشخص می‌کنند. می‌توانید فرض کنید که رأس ها از ‎$1$‎ تا ‎$n$‎ شماره‌گذاری شده اند.
  • در ‎$n-1$‎ سطر بعدی در هر سطر اطلاعات یک یال با دو عدد ‎$u_i$‎ و ‎$v_i$‎ مشخص شده است.
  • تضمین می‌شود که گراف داده شده در ورودی یک درخت را توصیف می‌کند.
  • ‎ $1 \leq n \leq 10^5$‎.
  • به ازای همه ‎$i$‎ ها، ‎$1 \leq s_i \leq 10^6$‎.

خروجی

در تنها سطر خروجی دو عدد چاپ کنید که عدد اول نشان دهنده تعداد چَک‌هایی است که سعید به فرتاش می‌زند و عدد دوم نشان دهنده تعداد چَک‌هایی است که فرتاش به سعید می‌زند.

زیرمسئله ها

  • زیرمسئله اول (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 20$‎.
  • زیرمسئله دوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 2\times 10^3$‎.
  • زیرمسئله سوم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 2\times 10^4$‎.
  • زیرمسئله چهارم (۲۵ نمره): در همه‌ی تست‌ها ‎$n\leq 10^5$‎.

محدودیت‌ها

  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3‎
1 2 3‎
1 2‎
2 3
0 1
3
1 3 3
1 2
2 3
1 1


ابزار صفحه