ก่อนอื่นให้ทำการหาเส้นทางแห่งความพยายาม การหาสามารถทำได้หลายวิธีเช่น DFS หรือ LCA

เมื่อหาเสร็จแล้วให้จินตนาการเส้นทางแห่งความพยายามเป็นเส้นตรงแนวนอน บนถนนนี้หลาย ๆ แห่งจะมี "ทางแยก" ที่พาออกไปจากเส้นทางแห่งความพยายาม

ให้เส้นทางแห่งความพยายามประกอบไปด้วยจุดยอด $u_1, u_2, u_3, ..., u_n$ และ $u_{i}$ และ $u_{i+1}$ ถูกเชื่อมด้วยถนนที่มีความยาว $L_{i}$ สำหรับ $1 \leq i \leq n-1$ สำหรับจุดยอด $u_i$ ใด ๆ ในเส้นทางแห่งความพยายามนี้ เรานิยาม $f(i)$ แทนเส้นทางที่ไกลที่สุดที่เริ่มต้นที่ $u_i$ ที่ไม่รวมเส้นทางแห่งความพยายาม

$f(i)$ สามารถคำนวณได้โดย DFS ในเวลา $\mathcal{O}(n)$

จากนั้นให้พิจารณาโครงสร้างของกราฟของเรา เส้นทางแห่งความพยายามสามารถเขียนแทนในรูป $u_1\ L_1\ u_2\ L_2\ ...\ u_{n-1}\ L_{n-1}\ u_n$ กำหนดให้ $S_i = L_1 + L_2 + \dots + L_i$ จะได้ระยะทางจาก $u_i$ ถึง $u_j$ เท่ากับ $S_{j-1}-S_{i-1}$

ดังนั้นสำหรับแต่ละคำถาม ให้ $i$ และ $j$ แทนตำแหน่งของเมืองของช่วงเริ่มต้นและสิ้นสุดตามที่ทีมงานประกาศและให้ $p$ และ $q$ เป็นตำแหน่งของเมืองที่เราจะพิจารณา โดย $i \leq p \leq q \leq j$ คำตอบของเราจะกลายเป็นค่าที่สูงสุดของ $f(p) + f(q) + S_{q-1} - S_{p-1}$ (กรณีที่เราเข้าเส้นทางแห่งความพยายามที่ $u_p$ และออกที่ $u_q$)

สังเกตว่าหากเรานิยาม $g(u) = f(u) + S_{u-1}$ และ $h(u) = f(u)-S_{u-1}$ เราจะต้องหาแค่ค่าที่มากที่สุดของ $h(p)+g(q)$ ได้ในเวลาเร็ว ๆ

เราสามารถทำเช่นนี้ได้โดยใช้ segment tree โดยสำหรับ node ที่แทนช่วงหนึ่ง ให้เราเก็บ

1. $h(i)$ ที่มากที่สุดของช่วงนี้
2. $g(i)$ ที่มากที่สุดของช่วงนี้
3. $h(i)+g(j)$ ที่ $i \leq j$ ที่มาุกที่สุดของช่วงนี้

การคำนวณข้อ 1, 2 ตอน merge จะค่อนข้างตรงไปตรงมา การคำนวณข้อ 3 สามารถทำได้โดยการใช้ค่า max ระหว่างข้อ 3 ของ node ลูกด้านซ้าย ข้อ 3 ของ node ลูกด้านขวา และข้อ 1 ของ node ลูกด้านซ้ายบวกกับข้อ 2 ของ node ลูกด้านขวา

ดังนั้นเราจะสามารถแก้โจทย์นี้ได้ในเวลา $\mathcal{O}(n\log n)$