سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲۲:سوال ۶
فهرست مندرجات
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 |
توضیحات
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
