ในข้อนี้เราได้รับต้นไม้มา หน้าที่ของเราคือการหาความยาวของ longest path บนต้นไม้ต้นนี้ โดยที่ความยาวของเส้นเชื่อมมีค่าเท่ากับความยุ่งเหยิงของเส้นเชื่อมนั้น ๆ

ก่อนอื่นให้เราทำการ root tree ที่จุดยอด $1$ โดยการมองจุดยอด $1$ เป็นรากของต้นไม้ แล้วให้จุดยอดอื่น ๆ ลดหลั่นกันลงมาตามเส้นทางจาก $1$ ไปหาจุดยอดนั้น ๆ

การ root tree จะทำให้จุดยอดใด ๆ ยกเว้นจุดยอด $1$ มี "parent" ของตัวมันเอง โดย parent คือจุดยอดแรกที่มันต้องผ่านในเส้นทางจากจุดยอดนั้น ๆ ถึง root เราจะแทน parent ของจุดยอด $u$ ด้วย $p(u)$

จากนั้นสำหรับจุดยอด $u$ ใด ๆ ที่ไม่ใช่ $1$ เราจะให้ $e(u)$ แทนเส้นเชื่อมที่เชื่อมระหว่าง $u$ และ $p(u)$

สังเกตว่าสำหรับจุดยอด $u$ ใด ๆ ถ้าเราตัดเส้นเชื่อม $e(u)$ ออก ต้นไม้ของเราจะถูกแบ่งออกเป็นสองส่วน คือ subtree ของ $u$ (รวม $u$ ด้วย) และ ส่วนที่เหลือของต้นไม้ โดยการจะเดินทางจากจุดยอดในส่วนหนึ่งไปหาจุดยอดในอีกส่วนหนึ่ง ต้องใช้ $e(u)$ เสมอ

ดังนั้นค่าความยุ่งเหยิงของ $e(u)$ จะมีค่าเท่ากับ $S(u)\cdot (n-S(u))$ เมื่อ $S(u)$ คือขนาดของ subtree ของ $u$ และ $n$ คือจำนวนจุดยอดทั้งหมดในต้นไม้ $S(u)$ สามารถคำนวณได้จาก $S(u) = 1 + \Sigma S(v)$ เมื่อ $v$ คือจุดยอดที่มี $u$ เป็น parent

ค่าความยุ่งเหยิงของเส้นเชื่อมทั้งหมดจะสามารถคำนวณได้โดย DFS ในเวลา $\mathcal{O}(n)$

จากนั้นเราจะต้องทำการหาเส้นทางที่ยาวที่สุดบนต้นไม้นี้ ซึ่งมีหลายวิธี แต่วิธีที่ผู้เขียนคิดว่าเรียบง่ายที่สุดคือวิธีการหา longest path สองครั้ง ซึ่งสามารถทำได้ดังนี้

• เริ่มที่จุดยอด $u$ ใด ๆ แล้วหาจุดยอดที่มีระยะทางไกลจาก $u$ มากที่สุด เรียกจุดยอดนี้ว่า $v$
• หาจุดยอดที่มีระยะทางไกลจาก $v$ มากที่สุด ระยะทางระหว่าง $v$ และจุดยอดนี้จะเป็น longest path บน tree

ทั้งสองขั้นตอนสามารถทำได้โดย Dijkstra's Algorithm หรือ DFS

ดังนั้นเราจะสามารถแก้ปัญหานี้ได้ในเวลา $\mathcal{O}(n)$