ให้ $m$ คือจำนวนบ้านที่เศรษฐีมีในตอนนี้ แน่นอนว่าถ้า $k \nmid m$ คำตอบจะเป็น NO เสมอ ดังนั้นเราจึงเหลือแค่กรณีที่ $k \mid m$

พิจารณาต้นไม้ $T$ ของเราในปัจจุบันที่มีขนาด $m$ เราจะทำการ root $T$ ที่ node หมายเลข 1 จากนั้นนิยาม $S(u)$ เป็นจำนวน node ใน subtree ของ $u$ (รวม $u$ ด้วย) ข้อสังเกตสำคัญในการแก้โจทย์ข้อนี้คือ "เศรษฐีจะสามารถแบ่งสมบัติตามที่โจทย์ต้องการก็ต่อเมื่อมีจุดยอด $u$ ที่ $k|S(u)$ จำนวน $m/k$ จุดพอดี"

ปัญหาของเราจึงกลายเป็นการเก็บและอัพเดทค่า $S(u)$ หลังจากบ้านแต่ละหลังถูกสร้างขึ้น หากเราแก้ปัญหานี้ตรง ๆ จะใช้เวลา $\mathcal{O}(n^2)$ ซึ่งจะไม่ทันเวลา

เพื่อที่จะ optimize อัลกอริธึมของเรา เราจะสร้าง tree ต้นเต็มเก็บไว้ก่อน จากนั้นในแต่ละจุดยอด $u$ เราจะมีอาเรย์ 1 มิติขนาด $k$ โดยเราจะเรียกอาเรย์นี้ว่า $T(u)$ โดยที่ $T(u)[i]$ จะเก็บ จำนวนจุดยอด $v$ ใน subtree ของ $u$ (รวม $u$ ด้วย) ที่ $S(v) \bmod k = i$

ในการเก็บและอัพเดทค่า $T(u)$ ให้เราสังเกตว่าในการสร้างบ้านใหม่แต่ละครั้ง จุดยอดที่มีค่า $T$ เปลี่ยนแปลงไปจะเป็นจุดยอดบน path จากจุดยอดหมายเลข 1 ถึงจุดยอดหมายเลข $u$ เท่านั้น ปัญหานี้จึงกลายเป็นปัญหา range update บน tree ซึ่งสามารถทำได้ใน $\mathcal{O}(\log n)$ โดย Heavy-Light Decomposition

เราจะตอบ YES ก็ต่อเมื่อ $T(1)[0] = m/k$

ในการอัพเดทใน segment tree ใน Heavy-Light Decomposition จะใช้เวลา $\mathcal{O}(k)$ ไปด้วย ทำให้เราสามารถแก้โจทย์ข้อนี้ในเวลา $\mathcal{O}(nk\log n)$