ข้อนี้ เป็นโจทย์ที่ให้ออกแบบโครงสร้างข้อมูลที่รองรับ 3 operations ดังนี้:

1. union(A, B) นำเครือข่ายทั้งหมดที่เชื่อมกับ A ไปต่อเข้ากับ B แล้วให้ master ฝั่ง A หายไป
2. setMaster(A) ย้าย master ในเครือข่าย A ให้เป็น A
3. query(A, B) รับประกันว่า (A, B) เป็นเส้นเชื่อมหนึ่งภายในบางเครือข่าย ให้หาว่าเครื่อง master ของเครือข่ายนั้นส่งผ่านมาสู่ A หรือ B ก่อน

เราเริ่มต้นจากการสังเกตว่า สำหรับการดำเนินการแบบที่ 3 นั้น หากเราทราบ master ของเครือข่ายนั้น และทราบระยะทางระหว่าง master ของเครือข่ายกับ A และ B คำตอบที่ได้คือจุดที่มีระยะห่างจาก master น้อยกว่าอีกจุด

สังเกตว่า โจทย์รับประกันว่าการกระทำแบบที่ 1 นั้น ไม่ทำให้เกิด cycle ในกราฟ แสดงว่าผลลัพธ์หลังจากทำทุก operations แล้วกราฟจะไม่มี cycle ใดๆ แสดงว่า ระยะห่างระหว่างเครื่อง u กับ v ใดๆ หากเชื่อมต่อกันแล้วจะไม่เปลี่ยนแปลงอีก (หากยังไม่เชื่อมต่อจะไม่นิยามระยะห่าง) เราจึงสมมติให้เกิดการเชื่อมต่อทุกอย่างจากการดำเนินการรูปแบบที่ 1 เรียบร้อยแล้ว เพื่อให้ง่ายต่อการเรียกใช้ จะขอตั้งชื่อกราฟนี้ว่า $F$ และ $F$ มีสมบัติคือสำหรับกราฟที่สร้างจากลำดับของการดำเนินการข้างต้น ณ เวลาใดๆ ระยะห่างระหว่างจุดใดๆ จะมีค่าเท่ากับระยะห่างใน $F$ หรือ ไม่นิยาม (กรณีไม่เชื่อมต่อกัน)

สมมติว่าเราไม่มีการดำเนินการรูปแบบที่ 2 เลย เราสามารถตอบคำถามในข้อนี้ได้โดยการสร้าง $F$ ก่อน (จากการทำการดำเนินการรูปแบบ 1 ทั้งหมด) หลังจากนั้นกลับมาสร้างใหม่ตั้งแต่ต้น โดยค่อยๆเชื่อมตามการดำเนินการ 1 และจำ master ของแต่ละ component ณ เวลาขณะใดๆ ด้วย (อาจใช้ Union-Find Data Structure เพื่อช่วยในการจำ โดยทำ path compression และให้ root แทน master) เมื่อพบการดำเนินการประเภทที่ 3 จากการจำดังกล่าวทำให้ทราบว่า master ปัจจุบันคือเครื่องใด (จะใช้ $M$ แทน master และ $A$, $B$ แทนเครื่องในคำถาม) ต่อมาเราต้องการทราบ $\argmin(dist(A,M), dist(B, M))$ (ให้ $dist(A,B)$ แทนระยะห่างระหว่างเครื่อง $A$ และ $B$) เราจะมีวิธีการหา $dist(A,M)$ และ $dist(B,M)$ บน $F$ ได้ดังนี้

เนื่องจาก $F$ นั้นไม่มี cycle แสดงว่า $F$ เป็น forest (ข้อควรระวัง: ในขณะที่ผู้เขียนทำโจทย์ข้อนี้ ผู้เขียนลืมไปว่าเป็น forest และคิดว่า $F$ เป็น tree จึงทำให้เกิดปัญหาตามมาหลายอย่าง) หลังจากนั้นเราจึงสามารถ สร้างเส้นเชื่อมบางเส้นเพื่อทำให้ $F$ กลายเป็น tree ได้ (โดยนำ component ต่างๆ มาเชื่อมกัน เพราะเราทราบแน่ๆว่าคำถามในรูปแบบ $dist(A, M)$ จะถามภายใน component เดียวกันเท่านั้น) เราจะเรียกกราฟนี้ว่า $F'$ หลังจากนั้นเราจึงสามารถใช้เทคนิค Lowest Common Ancestor (LCA) เพื่อ precompute ใน $\mathcal{O}(N \log N)$ สำหรับการหาระยะทางระหว่างสองจุดใดๆในกราฟ $F'$ ใน $\mathcal{O}(\log N)$

ณ จุดนี้ เราจะสามารถหาระยะห่างระหว่างสองจุดยอดใดๆใน $F$ ได้แล้ว จากการหา LCA บน $F'$ แล้วนำความลึกมาลบกัน (กล่าวคือ $dist(A, B) = depth_A + depth_B - 2 depth_{LCA(A,B)}$) เท่านี้ เราจะสามารถแก้โจทย์กรณีไม่มีการดำเนินการประเภท 2 ได้แล้ว

ต่อมาเราพัฒนาขั้นตอนวิธีการจัดเก็บ master ของแต่ละ component ดังนี้: จากเดิมที่ให้ Union-Find Data Structure เก็บ root แทน master เราจะเปลี่ยนเป็นเก็บค่า master ไว้ใน root

เมื่อมีการเชื่อมสอง components $A$, $B$ เราจะทราบได้เลยว่า master ของ $A$ คือ $root(A).{master}$ และ master ของ $B$ คือ $root(B).{master}$ เมื่อเชื่อม $A$ เข้าสู่ $B$ เราสามารถสั่งให้ $parent_{root(A)} = B$ ได้ ซึ่งทำให้ $root(A)$ มีค่าเท่ากับ $root(B)$ ซึ่งเท่ากับ parent ของ $root(A)$ เก่า

เมื่อมีการเปลี่ยน master ของ component ที่มีจุดยอด $A$ เราสามารถสั่งให้ $root(A).{master} = A$ ได้โดยง่าย

ที่เหลือก็เป็นการทำ path compression บน Union-Find Data Structure เพื่อลดเวลาการทำงาน

Overall Time Complexity: $\mathcal{O}((M + N) \log N)$