ข้อนี้ต้องมีพื้นฐานทฤษฎีกราฟและ dynamic programming จึงจะสามารถทำได้

โจทย์ให้ connect graph ที่มี $N - 1$ เส้นเชื่อม ดังนั้นกราฟดังกล่าวเป็นต้นไม้ (tree) โจทย์ถามว่า path ที่ label ของจุดสูงขึ้นเรื่อยๆ ที่ยาวประกอบไปด้วยกี่จุด

ลักษณะพิเศษของต้นไม้อย่างหนึ่งคือ ถ้าสองนิพจน์ดังต่อไปนี้เป็นจริง นิพจน์ที่เหลือจะต้องเป็นจริงด้วย

1. $G$ เป็น connected graph
2. $G$ มี $N - 1$ เส้นเชื่อม
3. ระหว่างสองจุดใดๆ จะมี path เดียวเชื่อมระหว่างสองจุดนั้น

ที่เป็นประโยชน์สำหรับข้อนี้ที่สุดคือนิพจน์ 3 เราสามารถ DFS จากแต่ละจุดและหา increasing path ทั้งหมดที่เริ่มจากจุดนั้นได้ โดยจะนำ increasing path ที่ยาวที่สุดที่หาเจอไปตอบ ทั้งหมดนี้ใช้เวลาคำนวณ $O(N^2)$ เนื่องจากต้องเริ่มจากแต่ละจุด (ทั้งหมดมี N จุด) และ DFS แต่ละครั้งใช้เวลา $O(N + M) = O(N + N - 1) = O(N)$ อย่างไรก็ตาม เนื่องจากค่า $N$ สูงสุดนั้นมากถึง 300,000 เราจึงไม่สามารถใช้อัลกอริทึมที่มีประสิทธิภาพเพียง $O(N^2)$ ได้

สังเกตุว่าถ้าหากเรากำหนด root ของต้นไม้เป็นจุดใหนก็ได้ (เพื่อความง่ายจะกำหนดเป็นจุด 1) โดยที่ความลึกของแต่ละจุดจะเท่ากับความห่างจากจุด 1 ดังนั้นpath ทั้งหมดจะแบ่งได้เป็นสองประเภท

1. path ที่ความลึกสูงขึ้นเรื่อยๆ
2. path ที่มี path ประเภทที่ 1 สอง path ประกบกัน

เราจะนิยามตัวแปร DP สองอย่าง

1. $max\_dec[v]$ = path ที่ยาวที่สุดที่เริ่มจาก v โดยที่ความลึกสูงขึ้นเรื่อยๆ (จาก v ลงจุดที่อยู่ด้านล่างเท่านั้น) และ label ของจุดลดลงเรื่อยๆ
2. $max\_inc[v]$ = เหมือนกัน $min\_dec[v]$ แต่ label ของจุดสูงขึ้นเรื่อยๆ

ถ้าเราต้องการ path แบบที่ 1 (path ที่ความลึกสูงขึ้นเรื่อยๆ) ที่ยาวที่สุด เราสามารถใช้ $max(max\_dec[v], max\_inc[v])$ ที่สูงสุดสำหรับทุก $v$ ตอบได้เลย

สำหรับ path แบบที่ 2 (path ที่มี path ประเภทที่ 1 สอง path ประกบกัน) จะใช้ค่า $max\_dec[v] + max\_inc[v] - 1$ ที่สูงสุดสำหรับทุก $v$ เพิ่มด้วย ที่ต้องลบ 1 เพราะว่า $v$ ถูกนับซ้ำใน $max\_dec[v]$ และ $max\_inc[v]$

ดังนั้นคำตอบสุดท้ายคือ $max(max\_dec[v], max\_inc[v], max\_dec[v] + max\_inc[v] - 1)$ ที่สูงสุดสำหรับทุก $v$ โดยที่ $max\_dec[v]$ และ $max\_inc[v]$ สามารถหาได้โดยใช้ DFS