แยกใหญ่ดาว

ก่อนอื่นให้เราพิจารณาโจทย์ข้อนี้เมื่อกราฟมีลักษณะเป็นเส้นตรง

ให้เรามองกราฟ ๆ นี้เป็นอาร์เรย์ โดยที่ตัวเลขในอาร์เรย์จะแทนระยะทางจากจุดยอดซ้ายสุดมาถึงจุดยอดนั้น ๆ

ให้ $A$ แทนอาร์เรย์นี้ เราจะได้ว่า ระยะทางจุดยอดที่ $i$ ไปหาจุดยอดที่ $j$ ตามลำดับของกราฟ โดย $i< j$ จะเท่ากับ $A[j]-A[i]$

ดังนั้นในการแก้โจทย์ข้อนี้สำหรับกรณีเส้นตรงเราสามารถไล่ fix จุดซ้าย $i$ ทุก ๆ จุด แล้วหาจำนวนจุดที่ระยะทางระหว่างจุดนี้ไม่เกิน $k$ คือทุก ๆ จุด $j$ อยู่ด้านขวาและมี $A[j] \leq A[i]+k$ การหาจำนวนจุดสามารถทำได้โดยการ binary search

เราจึงสามารถแก้ปัญหาในกรณีกราฟมีลักษณะเป็นเส้นตรงได้ใน $\mathcal{O}(n\log n)$

สำหรับกรณีที่กราฟไม่ได้เป็นเส้นตรง กราฟจะมีจุดยอดจุดเดียวที่มีเส้นเชื่อมมากกว่า 2 เส้น เราจะเรียกจุดนั้นว่า $R$

เส้นทางใด ๆ ในต้นไม้จะสามารถแบ่งออกเป็น 2 กรณี

เส้นทางที่ไม่ผ่าน $R$ หรือใช้ $R$ เป็นจุดปลาย
เส้นทางที่ผ่าน $R$ และไม่ใช้ $R$ เป็นจุดปลาย

สำหรับในกรณีแรก เส้นทางทั้งหมดในกรณีนี้จะเหมือนเส้นทางทั้งหมดในกรณีที่กราฟเป็นเส้นตรง ซึ่งเราเคยได้แก้ปัญหานี้ไว้แล้วข้างต้น

ในกรณีที่สอง เราจะต้องพิจารณาทีละ "สาย" ที่ออกมาจาก $R$ ให้ $d(u)$ แทนระยะทางจาก $R$ มาถึงจุดยอด $u$ จากนั้นสำหรับจุดยอด $u$ ใด ๆ เราจะต้องหาจำนวนจุดยอด $v$ ที่ $d(u) + d(v) \leq k$ และ $v$ ไม่ได้อยู่ในสายเดียวกับ $u$ ซึ่งสามารถทำได้เร็ว ๆ โดยใช้ data structure

ในการนับ สำหรับสาย ๆ หนึ่ง เราจะทำการหาจำนวนคู่ที่เป็นไปได้จากจุดยอดในสายนั้น ๆ ก่อน แล้วจึงทำการอัพเดทค่าระยะทางเข้าไปใน data structure ของเรา เพื่อที่ไม่ซ้ำกัน

data structure ของเราจำเป็นต้อง support operation ต่อไปนี้

เพิ่มตัวเลขเข้าไป
หาจำนวนตัวเลขในนั้นที่น้อยกว่าค่าหนึ่ง ๆ

data structure ที่เหมาะสมจึงเป็น Fenwick tree

ในการใช้ Fenwick tree เราจะทำการ coordinate compress ค่า $d(u)$ ทั้งหมดที่จำเป็นต้องใช้ก่อน จากนั้นให้เราเมื่อเราต้องการ update ให้หา index ที่เกี่ยวข้องกับค่านั้น แล้วทำการเพิ่มค่าลงไปใน Fenwick tree เมื่อเราจะหาจำนวนตัวเลขที่น้อยกว่าค่านั้น ๆ ให้เราหา sum ตั้งแต่ตำแหน่งแรกถึงตำแหน่งที่ค่านั้นเกี่ยวข้อง

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