+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که در طی ماه‌های اخیر عملکرد خیره‌کننده‌ای در کار و نظارتش بر دیگران داشت، توسط شرکت عمرانی سرداد به استخدام درآمد. شرکت عصر دانش‌افزار که در زمینه طراحی و ساخت اپلیکیشن‌های بانکی، مالی و خدمات پرداخت فعالیت دارد، کارهای نرم‌افزاری این شرکت عمرانی را انجام می‌دهد. در پروژه‌ای که به آقا فیروز داده‌ شده، $n$ روستا وجود دارد که از $1$ تا $n$ شماره‌گذاری شده‌اند. همچنین یک لیست شامل $n - 1$ جاده به آقا فیروز داده‌ شده که هر جاده دوتا از روستاها را به هم وصل می‌کند. تضمین می‌شود پس از احداث جاده‌ها می‌توان با پیمایش تعدادی جاده از هر روستایی به هر روستای دیگری رفت. همچنین در هر روستا، یک سوله وجود دارد که درون سوله واقع در روستای شماره $i$، دقیقا $i$ تن خاک وجود دارد. همچنین می‌دانیم برای احداث جاده‌ای بین دو روستای $u$ و $v$، باید **دقیقا از یکی از این دو روستا، دقیقا ۱ تن خاک** برداشت. حال آقا فیروز که تازه استخدام شده‌، می‌خواهد خودی نشان دهد. برای همین می‌خواهد تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک مورد نیاز جاده‌ها را بشمارد. اما به‌دلیل اینکه درگیر آنالیز کردن پروژه عمرانی‌اش است، از شما می‌خواهد تا به او در این موضوع کمک کنید. توجه کنید از آن‌جا که جواب ممکن است بزرگ باشد، جواب را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول برنامه عدد $n$ به شما داده می‌شود که بیانگر تعداد روستاها می‌باشد. در $n - 1$ خط بعدی، در هر خط دو عدد $u_i$ و $v_i$ می‌آید و بیانگر این است که جاده‌ای بین دو روستا با شماره‌های $u_i$ و $v_i$ باید احداث شود. تضمین می‌شود پس از احداث این $n - 1$ جاده، از هر روستایی با پیمایش جاده‌ها می‌توان به هر روستای دیگری رفت. $$1 \le n \le 1\ 000\ 000$$ $$1 \le u_i, v_i \le n$$ # خروجی در تنها خط خروجی، تعداد روش‌های مختلف انتخاب سوله‌ها برای برداشتن خاک را به باقیمانده $10^9 + 7$ بگویید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 1 3 ``` ## خروجی نمونه ۱ ``` 3 ``` می‌توان برای احداث جاده‌ی اول، از روستای شماره ۲ خاک برداشت، که در این‌صورت برای احداث جاده دوم می‌توان هم از روستای شماره ۱ و هم از روستای شماره ۳ خاک برداشت. همچنین اگر برای احداث جاده‌ی اول، از روستای شماره ۱ خاک برداریم، چون سوله واقع در روستای ۱، دقیقا یک تن خاک داشت، پس دیگر خاکی در آن باقی نمی‌ماند و مجبوریم از سوله واقع در روستای ۳ خاک برداریم. پس در کل به ۳ روش می‌توان سوله‌ها را برای برداشتن خاک انتخاب کرد. ## ورودی نمونه ۲ ``` 4 1 2 2 3 2 4 ``` ## خروجی نمونه ۲ ``` 7 ``` ## ورودی نمونه ۳ ``` 4 2 3 2 1 2 4 ``` ## خروجی نمونه ۳ ``` 7 ``` <details class="blue"> <summary> راهنمایی ۱ </summary> مسئله را به گراف تبدیل می‌کنیم. هم‌چنین به راسی که درجه‌اش بزرگ‌تر از اندیسش باشد، راس حساس می‌گوییم. می‌توانیم ثابت کنیم که تعداد راس‌های حساس از $O(\sqrt{n})$ است. حال اگر برای یک یال نتوانیم سوله‌ای انتخاب کنیم حتما دوسر آن یال، راس حساس هستند. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> درخت را از یک راس دلخواه (مانند راس یک) ریشه‌دار می‌کنیم‌ و جواب را برای هر زیردرخت حساب می‌کنیم. تعریف می‌کنیم: $dp_{1, u}$ یعنی جواب برای زیردرخت $u$، اگر در ابتدا در راس $u$ دقیقن $u$ تن خاک داشته باشیم. به همین طریق $dp_{2, u}$ نیز یعنی جواب برای زیردرخت $u$، اگر در ابتدا در راس $u$ دقیقن $u-1$ تن خاک داشته باشیم. برای راس‌های غیرحساس می‌دانیم $dp_{1, u}$ و $dp_{2, u}$ باهم برابرند و می‌توان به راحتی با مشخص کردن راس انتخاب‌شده روی یال بین بچه‌های $u$ و خودش مقدار آن‌ها را بدست آورد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> برای حساب کردن $dp_1$ و $dp_2$ برای راس‌های حساس، متغیری کمکی به نام $ans_{u, i}$ را حساب می‌کنیم که مقدار آن برابر با جواب برای زیردرخت راس $u$ بدون درنظر گرفتن بچه‌های غیرحساس آن است که می‌توان آن را با $O({deg_u}^2)$ حساب کرد ($deg_u$ برابر تعداد بچه‌های حساس راس $u$ است). از آنجا که مجموع $deg$ راس‌های حساس از $O(\sqrt{n})$ است، حساب کردن آن با $O(n)$ امکان‌پذیر است. حال با توجه به $ans_u$، می‌توان مقادیر موردنظر را حساب کرد. </details>

حل سؤال در بانک سؤالات