نجات (Rescue)
داروغه ناتینگهام که از ورودهای مخفیانه رابینهود بیزار شده بود، تصمیم گرفت تا هر روز رمز سری جدیدی را انتخاب کند و آن را به نگهبانان اطلاع دهد. داروغه هر روز یک درخت جدید را انتخاب میکند و سپس زیبایی آن را به عنوان رمز آن روز انتخاب میکند.
ارزش یک درخت با یالهای وزندار برابر بزرگترین مقسوم علیه مشترک وزن یالهایش ضربدر تعداد رئوسش است(اگر درخت تک رأسی باشد ارزشش صفر است). زیبایی یک درخت برابر با مجموع ارزش تمام زیرگرافهای القایی همبند1) آن است.
رابینهود امروز میخواهد برای نجات زندانیان راهی زندان شود اما سیستم رمز جدید داروغه برای او مشکل ایجاد کرده است. رابینهود پس از تلاشهای فراوان به درخت امروز دست پیدا کرده، اما به دلیل عدم تجربه در برنامهنویسی نمیتواند زیبایی آن را حساب کند، برای همین درخت را پیش شما آورده تا به او کمک کنید زندانیها را آزاد کند!
ورودی
در خط اول، تعداد رئوس درخت یا همان $n$ میآید.
در خطوط دوم تا $n$اُم، در هر خط سه عدد $u_i$, $v_i$ و $w_i$ آمده که به ترتیب دو سر یال و وزن آن را نشان میدهند.
خروجی
در تنها خط خروجی، مجموع ارزش تمام زیرگرافهای القایی همبند درخت ورودی را به پیمانهی $10^9 + 7$ را چاپ کنید.
زیرمسئلهها
- زیرمسئله اول (۷ نمره): $n\leq20$
- زیرمسئله دوم (۱۹ نمره): درخت ورودی مسیر است
- زیرمسئله سوم (۱۵ نمره): $n,w_i\leq2000$
- زیرمسئله چهارم (۱۰ نمره): $w_i=1$
- زیرمسئله پنجم (۲۱ نمره): وزن تمامی یالها توانی از ۲ هستند
- زیرمسئله ششم (۲۸ نمره): بدون محدودیت اضافی
محدودیتها
- $2 \leq n \leq 10^5$
- $1 \leq w_i \leq 10^5$
- $1 \leq u_i,v_i \leq n, u_i \neq v_i$
- تضمین میشود گراف ورودی درخت است.
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
4 1 2 2 2 3 6 3 4 3 | 41 |
4 1 2 6 1 3 10 1 4 15 | 96 |
شرح ورودی و خروجی نمونه
در ورودی اول، درختهایی یک یالی، دو یالی و سه یالی به عنوان زیرگراف القایی درخت اولیه داریم.
- ارزش درختهای تک یالی در مجموع برابر $2\times(2+6+3)=22$ است.
- درختهای دو یالی در این درخت دوتا هستند، که یکی از آنها ب.م.م. ۲ و دیگری ۳ دارد، پس در مجموع ارزش این درختها برابر $3\times(2+3)=15$
- تنها یک درخت سه یالی که داریم که ارزش آن برابر تعداد راسهایش یعنی $4$ است.
پس در مجموع زیبایی این درخت برابر $22 + 15+4=41$.
| < سوال قبل | سوال بعد > |