داروغه ناتینگهام که از ورودهای مخفیانه رابینهود بیزار شده بود، تصمیم گرفت تا هر روز رمز سری جدیدی را انتخاب کند و آن را به نگهبانان اطلاع دهد. داروغه هر روز یک درخت جدید را انتخاب میکند و سپس زیبایی آن را به عنوان رمز آن روز انتخاب میکند.
ارزش یک درخت با یالهای وزندار برابر بزرگترین مقسوم علیه مشترک وزن یالهایش ضربدر تعداد رئوسش است(اگر درخت تک رأسی باشد ارزشش صفر است). زیبایی یک درخت برابر با مجموع ارزش تمام زیرگرافهای القایی همبند1) آن است.
رابینهود امروز میخواهد برای نجات زندانیان راهی زندان شود اما سیستم رمز جدید داروغه برای او مشکل ایجاد کرده است. رابینهود پس از تلاشهای فراوان به درخت امروز دست پیدا کرده، اما به دلیل عدم تجربه در برنامهنویسی نمیتواند زیبایی آن را حساب کند، برای همین درخت را پیش شما آورده تا به او کمک کنید زندانیها را آزاد کند!
در خط اول، تعداد رئوس درخت یا همان $n$ میآید.
در خطوط دوم تا $n$اُم، در هر خط سه عدد $u_i$, $v_i$ و $w_i$ آمده که به ترتیب دو سر یال و وزن آن را نشان میدهند.
در تنها خط خروجی، مجموع ارزش تمام زیرگرافهای القایی همبند درخت ورودی را به پیمانهی $10^9 + 7$ را چاپ کنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
4 1 2 2 2 3 6 3 4 3 | 41 |
4 1 2 6 1 3 10 1 4 15 | 96 |
در ورودی اول، درختهایی یک یالی، دو یالی و سه یالی به عنوان زیرگراف القایی درخت اولیه داریم.
پس در مجموع زیبایی این درخت برابر $22 + 15+4=41$.