====== محاسبه‌ی قطر و مرکز درخت ======


===== تعریف =====

طولانی‌ترین مسیر موجود در درخت را قطر آن و رأسی که بیشینه فاصله‌اش از سایر رئوس کمینه باشد را مرکز آن می‌نامیم.

برای به‌دست آوردن قطر درخت، کافیست لم زیر را در نظر بگیریم؛

لم:‌ اگر راس v بیش‌ترین فاصله را از رأس u داشته باشد، قطری وجود دارد که v یکی از دو سر آن باشد. همچنین اگر x , y دو سر یک قطر باشند، به ازای هر رأس مانند u، یکی از دو سر قطر دارای بیش‌ترین فاصله از u می‌باشد.

حال کافیست از رأس دلخواه u، با استفاده از یکی از پیمایش‌ها مانند پیمایش سطح‌اول، دورترین رأس را بیابیم و آن را x بنامیم. سپس بار دیگر از رأس x دورترین رأس را بیابیم و آن را y بنامیم. حال بنابر لم بالا، مسیر xy یک قطر از درخت می‌باشد.





===== الگوریتم =====


===== پیچیدگی‌ الگوریتم =====


===== پیاده‌سازی اولیه =====

<code c A.c>
#include <iostream>
int main() {
}
</code>

===== پیاده‌سازی سریع‌تر =====

<code c ‌‌B.c>
#include <iostream>
int main() {
}
</code>


===== کابردها =====


**مثال**:
صورت مسئله اینجا می‌آید.

<پاسخ>

پاسخ مسئله اینجا می‌آید

</پاسخ>


===== مسائل نمونه =====


  * [[سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۴:عملی_مقدماتی_اول:سوال_۱|سوال عملی دوره‌ی تابستان ۲۴]] [سطح: ساده]
===== مراجع =====

  * [[http://e-maxx.ru/algo/euler_function|تابع اویلر - سایت ماکزیمال]]
  * [[http://en.wikipedia.org/wiki/Euler%27s_totient_function|تابع اویلر - ویکی‌پدیا]]