سلام دوست عزیز😃👋

به مسابقه «کدکاپ ۸ - انتخابی ۶» خوش آمدی!

  • اگر تا الان سوالی در سیستم داوری کوئرا حل نکردید حتماً نحوه‌ی کار با ورودی و خروجی را یاد بگیرید.
  • اگر ابهامی درباره‌ی قوانین شرکت در مسابقات این قسمت را بخوانید تا از شما تقلب گرفته نشود.
  • از قوانین مهم اینکه هرگونه استفاده از ابزارهای آماده‌ی تولید کد مثل chatGPT و یا تبادل کد با سایر شرکت‌کنندگان مسابقه ممنوع است و منجر به حذف شما از رقابت می‌شود.
  • برای اطلاع بیشتر از خطاهایی که سیستم داوری به شما می‌دهد این لینک را مطالعه کنید.
  • می‌توانید سوال‌ها و مشکلات خود را از بخش سوال بپرسید با ما در میان بگذارید.

موفق باشید و بهتون خوش بگذره 😉✌

⚡راستی! امشب ساعت ۱۹:۳۰ کلاس آنلاین حل سوالات مسابقه توی این لینک برگزار می‌شه و از هر استان، به ۳ نفر از شرکت‌کنندگان، دوره‌های دلخواه مقدماتی و یا پیشرفته کوئراکالج هدیه می‌شه.🎁

جایزه به استاندار


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

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

توضیح تصویر

جاده‌های این کشور دو طرفه‌اند و بین دو استان کشیده شده‌اند. می‌دانیم اگر از هر استان کشور کدکاپ شروع کنیم می‌توانیم با رفتن به استان‌های همسایه، به تمام استان‌های کشور برسیم. همچنین تعداد جاده‌ها بسیار کم است و به اندازه حداقل تعداد جاده برای رسیدن از تمام استان‌ها به استان‌های دیگر طراحی شده است. می‌توان اثبات کرد که همیشه تعداد جاده‌ها یکی کمتر از تعداد استان‌ها است.

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

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت tt آمده که تعداد سناریوها را نشان می‌دهد. سپس در ادامه برای هر سناریو به ترتیب ورودی‌ها داده می‌شوند. 1t3000001 \leq t \leq 300 \, 000

در سطر اول هر سناریو عدد صحیح و مثبت nn که نشانگر تعداد شهرها در سناریو iiام است ورودی داده می‌شود. سپس در n1n - 1 خط بعدی جاده‌های کشور ورودی داده می‌شوند، در هر خط دو عدد صحیح و مثبت viv_i و uiu_i داده می‌شود که دو استان مبدا و مقصد جاده را مشخص می‌کنند.

1n3000001 \leq n \leq 300 \, 000 1ui,vin1 \leq u_i, v_i \leq n

تضمین می‌شود که مجموع nn روی همه‌ی سناریوها حداکثر ۳۰۰،۰۰۰ باشد.

خروجی🔗

خروجی tt سطر دارد که برای هر سناریو، در یک خط کمترین میزان سکه برای جایزه دادن به کل استان‌ها را باید چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

2
2
2 1
8
7 3
4 6
1 7
5 4
7 4
2 7
8 4
Plain text

خروجی نمونه ۱🔗

3
11
Plain text
توضیح نمونه ۱

توضیح تصویر

اگر به استان ۱، 11 سکه و به استان ۲، 22 سکه داده شود، هیچ دو استان مجاوری تعداد یکسانی سکه دریافت نمی‌کنند و این کمترین مجموع سکه ممکن را دارد. بنابراین پاسخ برابر 1+2=31 + 2 = 3 است.

توضیح نمونه ۲

توضیح تصویر

اگر به استان ۱، ۲، ۳، ۵، ۶ و ۸ 11 سکه و به استان ۴، 22 سکه و به استان ۷، 33 سکه داده شود، هیچ دو استان مجاوری تعداد یکسانی سکه دریافت نمی‌کنند و این کمترین مجموع سکه ممکن را دارد. بنابراین پاسخ برابر 6×1+2+3=116 \times 1 + 2 + 3 = 11 است.

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.