سرویس (Service)
امیرمحمد یک گراف وزندار همبند $n$ راسی با $m$ یال ($m > n$) دارد. در گراف وزن یال بین دو راس $x$ و $y$ را با $w_{x,y}$ نمایش میدهیم. او شروع به بازی با این گراف میکند. در هر گام یک راس مثل $x$ که درجهاش دقیقا $2$ است (یعنی دو یال به این راس متصل است) و دو همسابه متمایز $y$ و $z$ دارد را انتخاب میکند و این راس و یالهای متصل به آن را حذف میکند. سپس یک یال بین دو راس $y$ و $z$ با وزن $max(w_{x,y}, w_{x, z})$ قرار میدهد. اما امیرمحمد خیلی کنترلی روی اعصابش ندارد و یک راس تصادفی $x$ انتخاب میکند و عملیات بالا را روی آن انجام میدهد (با احتمال یکسان بین انتخاب های ممکن). میدانیم امیرمحمد $k$ بار این کار را انجام داده است. امید ریاضی مجموع وزن یالهای درخت فراگیر کمینه (MST) گراف حاصل را پس از انجام $k$ مرحله بیابید. فرض کنید پاسخ به صورت $\frac{P}{Q}$ باشد که $gcd(P, Q) = 1$. شما حاصل $P \times Q^{-1} \mod (10^9 + 7)$ را نمایش دهید. تضمین میشود که در گراف داده شده در هر حالتی میتوان $k$ بار چنین عملیاتی را انجام داد.
ورودی
سطر اول ورودی شامل سه عدد $n$ و $m$ و $k$ است. سپس در $m$ سطر بعدی، در هر سطر سه عدد $u_i$ و $v_i$ و $w_i$ آمده است که بیانگر یک یال بین $u_i$ و $v_i$ با وزن $w_i$ است.
خروجی
در تنها سطر خروجی خواسته مسئله را چاپ کنید.
محدودیتها
- $1 \le k < n < m \le 5 \times 10^{5}$.
- $m \le \frac{n \times (n-1)}{2}$.
- $1 \le u_i, v_i \le n$.
- $1 \le w_i \le 10^9$.
- $u_i \neq v_i$.
- گراف در ابتدا یال چندگانه ندارد ولی ممکن است پس از انجام عملیات گفتهشده یال چندگانه بهوجود بیاید.
زیرمسئلهها
- زیرمسئله اول (۱۳ نمره): $n \le 15$.
- زیرمسئله دوم (۲۰ نمره): $n \le 100$.
- زیرمسئله سوم (۲۰ نمره): $n \le 2000$.
- زیرمسئله چهارم (۴۷ نمره): بدون محدودیت اضافی.
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
4 5 1 1 2 1 2 3 2 3 1 3 1 4 4 2 4 4 | 4 |
6 7 1 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 1 6 1 4 7 | 12 |
4 5 1 1 2 1 2 3 1 3 1 1 1 4 2 2 4 2 | 500000006 |
6 7 2 1 2 1 2 3 2 3 4 3 4 5 4 5 6 5 6 1 6 1 4 7 | 9 |
توضیحات نمونهها
- در نمونه اول با احتمال $\frac{1}{2}$ راس $3$ انتخاب میشود و سپس پس از عملیات وزن زیر درخت کمینه فراگیر $5$ میشود. با احتمال $\frac{1}{2}$ راس $4$ انتخاب میشود و سپس پس از عملیات وزن زیر درخت کمینه فراگیر $3$ میشود. پس امید ریاضی $4$ است.
- در نمونه دوم $4$ حالت انتخاب داریم و وزنهای درخت کمینه $10, 11, 13, 14$ میشود. لذا امید ریاضی برابر با $12$ است.
- در نمونه سوم در حالتی که عملیات روی راس $3$ اجرا شود جواب $3$ است. در حالتی که عملیات روی راس $4$ انجام شود، جواب $2$ است. بنابراین پاسخ نهایی $\frac{3}{2} + \frac{2}{2} = \frac{5}{2}$. $\frac{5}{2} \equiv 5 \times 500000004 \equiv 500000006 \ \mod (10^9 + 7)$