+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + روز ۳ دوره ۳۱ ---------- جک پس از اینکه گاو خود را با لوبیای سحرآمیز پیر دانا عوض کرد، آن را کاشت و سپس خوابید. روز بعد که بیدار شد دید که لوبیا رشد کرده و تبدیل به یک درخت عجیب شده است. این درخت دارای $n$ لوبیا است که هر لوبیا یک خوشمزگی از $1$ تا $n$ دارد و به ازای هر عدد از $1$ تا $n$ دقیقا یک لوبیا با آن خوشمزگی وجود دارد. به لوبیا با خوشمزگی $i$ لوبیای $i$ می‌گوییم. در این درخت دقیقا $n-1$ چوب وجود دارد که چوب $i$م لوبیا $u_i$ و $v_i$ را به هم وصل می‌کند. می‌گوییم دو لوبیا $x$ و $y$ به هم مسیر دارند اگر و تنها اگر دنباله‌ای از لوبیا‌ها مانند $\langle a_1, a_2, ..., a_k\rangle$ وجود داشته باشد که $a_1 = x, a_k = y$ و بین هر دو عضو متوالی از این دنباله چوب وجود داشته باشد. میدانیم که پیر دانا تضمین کرده که بین هر دو لوبیا مسیر وجود دارد. حال مادر جک میخواهد برای ناهار قورمه‌سبزی(!) درست کند و برای این کار می‌خواهد تعدادی از لوبیا‌های درخت را بکَنَد و با آنها غذا درست کند. اگر او بخواهد لوبیای $i$ را بکَنَد مجبور است تمام چوب‌های متصل به آن را نیز بشکند. طبق دستور پختی که از مادربزرگ جک به مادر جک رسیده نباید در قورمه‌سبزی طعم لوبیا‌ها تفاوت داشته باشند. برای همین او دو عدد $l$ و $r$ انتخاب می‌کند که $1 \leq l \leq r \leq n$ باشد. سپس تمامی لوبیا‌هایی که خوشمزگی آنها بین $l$ و $r$ است (شامل خود $l$ و $r$) را می‌کَنَد و در غذا می‌ریزد. پیر دانا که توانسته بود پیش‌بینی کند که مادر جک می‌خواهد با لوبیا‌های درخت سحرآمیز قورمه‌سبزی درست کند به مادر جک هشدار داد که این درخت جادویی است و اگر پس از کندن لوبیاها، لوبیایی باقی نماند یا اینکه دو لوبیا باقی بمانند که به هم مسیر نداشته باشند، درخت جک و مادرش را نفرین می‌کند و به سنگ تبدیل می‌کند !! مادر جک بسیار ترسید که سنگ شود ولی از آنجایی که آدم گرسنه از چیزی نمی‌ترسد از درست کردن قورمه‌سبزی منصرف نشد. حال پیر دانا که بسیار نگران جک و مادرش است می‌خواهد بداند که مادر جک به چند طریق می‌تواند دو عدد $l$ و $r$ را انتخاب کند که سنگ نشوند. از آنجایی که در روستا کامپیوتر وجود ندارد، پیر دانا از شما میخواهد برنامه‌ای بنویسید که جواب پرسش پیرمرد را بدهد.\\ پیر دانا به شما توصیه می‌کند که به ورودی‌های نمونه توجه کنید تا خواسته‌ی او را بهتر متوجه شوید. # ورودی در خط اول ورودی عدد $n$ که تعداد لوبیا‌های درخت است داده می‌شود. در $n-1$ خط بعدی ورودی در خط $i$م دو سر چوب‌های درخت‌ به ترتیب داده می‌شوند. در خط $i$ دو عدد$u_i$ و$v_i$ داده می‌شود که یعنی چوبی بین لوبیا‌ی $u_i$ و $v_i$ وجود دارد. $$1 \leq n \leq 10^6$$ $$1 \le u_i, v_i \le n~~,~~ u_i \neq v_i$$ بین هر دو لوبیا مسیر وجود دارد. # خروجی در خروجی تنها یک عدد خروجی دهید که برابر تعداد جفت $l$ و $r$ است که با کندن آنها جک و مادرش نفرین نمی‌شوند. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳ | $1 \leq n \leq 300$ | | ۲ | ۵ | $1 \leq n \leq 3000$ | | ۳ | ۱۰ | تعداد لوبیاهایی که حداقل 2 شاخه به آنها متصل است، حداکثر $3000$ است. | | ۴ | ۱۹ | درخت سحرآمیز به شکل یک مسیر است. (به هر راس حداکثر 2 چوب متصل است). | | ۵ | ۱۶ | $1 \leq n \leq 10^5$ | | ۶ | ۲۱ | اگر به ازای هر $i$ کوتاه ترین مسیر از لوبیای $1$ به لوبیای $i$ را درنظر بگیریم خوشمزگی لوبیا‌ها صعودی است. | | ۷ | ۲۶ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 1 2 2 4 3 4 ``` ## خروجی نمونه ۱ ``` 6 ``` لوبیاها را با دایره و چوب‌ها را با خط نشان دهیم. اگر لوبیاهای کنده شده را با ضربدر مشخص کنیم، حالت‌های مطلوب نمونه ورودی اول 6 حالت زیر می‌باشد.  و برای مثال حالت زیر نامطلوب است چون لوبیای شماره $1$ به لوبیای شماره $3$ مسیر ندارد.  ## ورودی نمونه ۲ ``` 6 1 6 6 5 5 2 1 3 4 1 ``` ## خروجی نمونه ۲ ``` 10 ``` ## ورودی نمونه ۳ ``` 9 1 3 9 2 3 5 2 4 7 4 1 2 1 8 3 6 ``` ## خروجی نمونه ۳ ``` 23 ```

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