المپدیا

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

ابزار کاربر

ابزار سایت


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

Tree

یک درخت ‎$n$‎ راسی به شما داده شده است. روی هر یک از یال های درخت عددی بین ‎$1$‎ و ‎$n-1$‎ نوشته شده و همه این اعداد متمایز هستند. به مسیر بین دو راس ‎$i$‎ و ‎$j$‎ ‎ مناسب می‌گوییم ‎ اگر

  • $i$‎ و ‎$j$‎ متفاوت باشند
  • ‎ هیچ کدام از اعداد نوشته شده بر روی یال های مسیر بر دیگری بخشپذیر نباشد

شما باید برنامه‌ای بنویسید که با دریافت اطلاعات درخت تعداد میسرهای مناسب آن را پیدا کند‎.

ورودی

  • در سطر اول ورودی، عدد ‎$n$‎، تعداد رئوس درخت قرار دارد.
  • در ‎$n-1$‎ سطر بعدی در هر سطر به ترتیب سه عدد ‎$u$‎ ، ‎$v$‎ و ‎$c$‎ آمده است که نشان می‌دهد یک یال بین دو راس ‎$u$‎ و ‎$v$‎ درخت قرار دارد که عدد نوشته شده روی آن ‎$c$‎ است‎.‎
  • همه‌ی اعداد نوشته شده روی یال‌های درخت متفاوت و بین ‎$1$‎ و ‎$n-1$‎ هستند. هم‌چنین ورودی یک درخت را توصیف می‌کند.‎
  • ‎$1 \le n \le 100000$‎
  • در حداقل ‎$40$‎ درصد تست‌ها ‎$n$‎ از ‎$3000$‎ بیش‌تر نیست.‎

خروجی

در تنها سطر خروجی پاسخ سوال را چاپ نمایید.‎

محدودیت‌ها

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

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

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

توضیحات

در مثال نمونه مسیرهای بین رئوس ‎$(1,2)$‎ ، ‎$(1,3)$‎ ، ‎$(2,3)$‎ و ‎$(2,4)$‎ مناسب هستند‎.


ابزار صفحه