====== مست (MST) ====== سپس از هرس کردن درخت در روز قبل، آشمز علاقه‌ی زیادی به درختان پیدا کرده است. او تصمیم می‌گیرد روی درخت $n$ راسی جدیدش سوال زیر را مطرح کند: فرض کنید $k$ تا از راس‌های درخت را علامت‌دار کردیم. سپس گراف کامل $k$ راسی $G$ را تعربف می‌کنیم که راس‌هایش متناظر با راس‌های علامت‌دار درخت هستند، و وزن یال بین راس‌های $v$ و $u$ برابر با فاصله‌ی این دو راس در درخت اصلی می‌باشد. حال امتیاز این درخت علامت‌دار را $MST(G)$ تعریف می‌کنیم. از آنجایی که آشمز فکر می‌کند سطح این سوال پایین است، جمع امتیاز تمام درخت‌های علامت‌دار، بین هر $2^n$ حالت ممکن را می‌خواهد. در این سوال شما باید پاسخ این سوال را به پیمانه‌ی $10^9 + 7$ محاسبه و چاپ کنید. ===== ورودی ===== در خط اول ورودی عدد طبیعی $n$ تعداد راس‌های درخت می‌آید. در هر یک از $n - 1$ خط بعدی دو عدد $v$ و $u$ به ترتیب می‌آیند که نشان‌دهنده‌ی یالی بین $v$ و $u$ است. ===== خروجی ===== خروجی برنامه شامل یک خط است که جمع امتیاز تمام $2^n$ درخت علامت‌دار ممکن را به پیمانه‌ی $10^9 + 7$ نشان می‌دهد. ===== زیرمسئله‌ها ===== * زیرمسئله اول (۱۵ نمره): $n \leq 22$ * زیرمسئله دوم (۱۵ نمره): به جز یک راس، به هر راس حداکثر دو یال متصل است. * زیرمسئله سوم (۳۵ نمره): $n \leq 1000$ * زیرمسئله چهارم (۳۵ نمره): بدون محدودیت اضافی ===== محدودیت‌ها ===== * محدودیت زمان: ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت * $1 \leq n \leq 5000$ * $1 \leq v, u \leq n$ * تضمین می‌شود یال‌ها تشکیل درخت می‌دهند. ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 \\ 1 2 \\ 2 3|6| |7 \\ 3 1 \\ 1 2 \\ 3 5 \\ 4 5 \\ 3 6 \\ 6 7| 496| * [[سوال ۸|سوال قبل]]