فهرست مندرجات
Spy
سازمان اطلاعات کشور ایکو، برای جمع‌آوری اطلاعات، $n$ جاسوس به کشور بیکو فرستاده است. این جاسوس‌ها با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند و برای ارتباط با یکدیگر از تلفن‌های همراه مخصوصی استفاده می‌کنند. به دلیل مسائل امنیتی، برقراری ارتباط تنها بین $n-1$ جفت از جاسوس‌ها مجاز است. هم‌چنین می‌دانیم گرافی که راس‌های آن جاسوس‌ها باشند و یال‌های آن، جفت جاسوس‌هایی باشند که می‌توانند با یکدیگر ارتباط تلفنی برقرار کنند، یک درخت است.
در این ارتباط‌ها، هر جاسوس یک کد دارد که در برقراری ارتباط با دیگر جاسوس‌ها از آن استفاده می‌کند. (دقت کنید که کد جاسوس $i$ $(1\leq i\leq n)$ ، می‌تواند $i$ نباشد). کد جاسوس‌ها یک عدد طبیعی از $1$ تا $n$ است و هم‌چنین کد هر دو جاسوسی متفاوت است. به خاطر دلایل نامعلوم، سازمان اطلاعات برای هر جفت جاسوس $(i,j)$ که می‌توانند با هم ارتباط برقرار کنند، مشخص کرده است که کد کدام یک از دو جاسوس باید کوچک‌تر باشد.
برنامه‌ای بنویسید که با گرفتن ارتباط‌های مجاز بین جاسوس‌ها و این‌که در هر ارتباط مجاز، کد کدام یک از آن‌ها باید کمتر باشد، تعداد روشهای اختصاص‌دهی کد به جاسوس‌ها را محاسبه کند. با توجه به این‌که این عدد ممکن است بزرگ باشد، برنامه‌ی شما باید باقی‌مانده این عدد بر $10^9+7$ را به عنوان جواب در نظر بگیرد.
ورودی
سطر اول ورودی شامل عدد طبیعی $n$، تعداد جاسوس‌ها، است.
در هر یک از $n-1$ سطر بعدی به ترتیب دو عدد $u$ و $v$ آمده است که به معنای این است که جاسوس $u$ و $v$ می‌توانند با هم ارتباط تلفنی برقرار کنند و هم‌چنین کد جاسوس $u$ باید کمتر از کد جاسوس $v$ باشد.
خروجی
در تنها سطر خروجی، باقی‌مانده‌ی تعداد روشهای کدگذاری جاسوس‌ها بر $10^9+7$ را چاپ کنید.
زیرمسئله‌ها
- زیرمسئله اول (۱۲ نمره): $n\leq 11$
- زیرمسئله دوم (۳۷ نمره): $n\leq 300$
- زیرمسئله سوم (۵۱ نمره): بدون محدودیت اضافی
محدودیت‌ها
- $1\leq n\leq 3000$
- $1\leq u,v\leq n$, $u\neq v$
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 1 2 2 3 | 1 |
| 4 1 4 2 4 3 4 | 6 |
شرح ورودی و خروجی نمونه
در ورودی نمونه‌ی اول، تنها کدگذاری مجاز این است که به جاسوس $i$ کد $i$ اختصاص داده شود.
در ورودی نمونه‌ی دوم، باید به جاسوس $4$، کد $4$ اختصاص داده شود. با توجه به این‌که محدودیتی روی ترتیب کد‌های جاسوس‌های $1$، $2$ و $3$ وجود ندارد، بنابراین کد‌های $1$، $2$ و $3$ به هر ترتیبی می‌توانند به این جاسوس‌ها اختصاص داده شوند. بنابراین $3!=6$ حالت مجاز برای اختصاص‌دهی کد به جاسوس‌ها وجود دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
