قضیه: به ازای هر درخت $T$ و راس $u$، اگر $v$ راسی باشد که فاصله آن از $u$ بیشینه باشد، یکی از بلندترین مسیرهای گراف از $v$ شروع می‌شود.

با استفاده از این قضیه می‌توان نشان داد اگر درخت $T_2$ برابر باشد با درختی که از اضافه کردن برگ $l$ به درخت $T_1$ ساخته می‌شود و بزرگ‌ترین مسیر درخت $T_1$ بین دو راس $u$ و $v$ باشد، بزرگ‌ترین مسیر درخت $T_2$ یکی از سه مسیر $(u,v)$ ، $(u,l)$ و $(v,l)$ خواهد بود.

پس اگر ما بتوانیم فاصله هر دو راس $(u,v)$ را در زمان ${\cal O}(\log n)$ به‌دست بیاوریم، می‌توانیم با اضافه کردن هر راس به درخت، بلندترین مسیر آن را در زمان ${\cal O}(\log n)$ به‌روز کنیم و اندازه آن را چاپ کنیم.

برای این کار ابتدا درخت $T$ که شامل تمام $n$ راس است را می‌سازیم و درخت را از راس $1$ به صورت زیر پیمایش می‌کنیم:

پیمایش راس $u$

• $u$ را به لیست $l$ اضافه کن
• به‌ازای هر فرزند $v$ از راس $u$:
  • راس $v$ را پیمایش کن
  • $u$ را به لیست $l$ اضافه کن

اگر $dep$ هر راس برابر با فاصله آن راس از راس شماره $1$ باشد، فاصله دو راس $list[i]$ و $list[j]$ برابر خواهد بود با:

$$dep[list[i]] + dep[list[j]] - min(dep[list[i]],dep[list[i+1]],\cdots,dep[list[j]])$$

پس کافیست به‌ازای هر راس یکی از مکان‌هایی که در لیست قرار دارد را ذخیره کنیم و مقادیر $dep[list[i]]$ ها را در یک segment tree ذخیره کنیم تا بتوانیم فاصله هر دو راس را در زمان ${\cal O}(\log n)$ به‌دست بیاوریم.

پیچیدگی: به‌دست آوردن مقادیر $dep$ راس‌ها را می‌توان در ${\cal O}(n)$ انجام داد و فاصله هر دو راس را می‌توان در زمان ${\cal O}(\log n)$ به‌دست آورد ، هم‌چنین ساختن لیست $l$ در زمان ${\cal O}(n)$ انجام می‌شود. پس کل کار در زمان ${\cal O}(n \log n)$ انجام می‌شود.