แผนการเรียน
/

Tree Algorithms Practice
ภาคปฏิบัติ: เส้นผ่านศูนย์กลาง, บรรพบุรุษ และระยะทาง

Day 06: 15.00 - 17.00 น. | เน้นการแก้โจทย์บน CSES และ AtCoder

โจทย์หลักที่จะฝึกฝน

Tree Diameter: การหาเส้นทางที่ยาวที่สุด
K-th Ancestor: การสืบค้นบรรพบุรุษในเวลา logarithmic
Lowest Common Ancestor (LCA) & Distances

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

โจทย์ 1: Tree Diameter

"จงหาระยะทางที่ยาวที่สุดระหว่างโหนด 2 โหนดใดๆ ในต้นไม้ที่มี ( n ) โหนด"

ตัวอย่างโจทย์: https://cses.fi/problemset/task/1131

  • ข้อมูลนำเข้า: รายการเส้นเชื่อม ( n-1 ) เส้น
  • ข้อจำกัด: ( n \le 2 \cdot 10^5 )
  • เวลาที่กำหนด: 1.0 วินาที

แนวทางแก้ปัญหา: Tree Diameter

วิธี DFS 2 ครั้ง

1. DFS จากโหนด ( a ) ใดๆ เพื่อหาโหนด ( b ) ที่ไกลที่สุด
2. DFS จากโหนด ( b ) เพื่อหาโหนด ( c ) ที่ไกลที่สุด
3. ระยะทาง ( dist(b, c) ) คือคำตอบ

วิธี Dynamic Programming

สำหรับแต่ละโหนด ( x ) ให้คำนวณ:
- ( toLeaf(x) ): เส้นทางยาวสุดไปหาใบ
- ( maxLength(x) ): เส้นทางยาวสุดที่มี ( x ) เป็นจุดสูงสุด

เพิ่มเติม: https://cses.fi/book/book.pdf (Chapter 14.2)

โจทย์ 2: K-th Ancestor

"จงหาบรรพบุรุษลำดับที่ ( k ) ของโหนด ( x ) ในต้นไม้ที่มีราก (Rooted Tree)"

ตัวอย่างโจทย์: https://cses.fi/problemset/task/1687

คำถามมีจำนวนมาก ( ( q ) คำถาม) หากเดินขึ้นทีละขั้นจะใช้เวลา ( O(k) ) ต่อคำถาม ซึ่งจะทำให้เกิด Time Limit Exceeded (TLE)

แนวทางแก้ปัญหา: Binary Lifting

Preprocessing ( O(n \log n) ):

สร้างตาราง ( up[v][k] ) เพื่อเก็บโหนดบรรพบุรุษลำดับที่ ( 2^k )

up[v][k] = up[up[v][k-1]][k-1]

Query ( O(\log k) ):

แตกค่า ( k ) เป็นเลขฐานสอง แล้ว "กระโดด" ขึ้นไปตามตำแหน่งบิตที่เป็น 1

ศึกษาเทคนิค: https://usaco.guide/gold/LCA

โจทย์ 3: Lowest Common Ancestor (LCA)

"จงหาโหนดที่เป็นบรรพบุรุษร่วมที่อยู่ลึกที่สุดของโหนด ( a ) และ ( b )"

ตัวอย่างโจทย์: https://cses.fi/problemset/task/1135

เป็นปัญหาพื้นฐานที่ใช้ในการหาระยะทางระหว่างโหนดและตรวจสอบความสัมพันธ์ในกราฟต้นไม้

แนวทางแก้ปัญหา: LCA Algorithm

ขั้นตอนการหา LCA(a, b):

  1. ปรับระดับ (Lift) โหนดที่ลึกกว่าขึ้นมาให้มีความลึกเท่ากับอีกโหนดหนึ่ง
  2. ถ้าโหนดทั้งสองเป็นโหนดเดียวกันแล้ว ให้ตอบโหนดนั้นทันที
  3. ถ้ายังไม่ใช่ ให้ลองกระโดดขึ้นไป ( 2^k ) ขั้นพร้อมกัน โดยเงื่อนไขคือต้องไม่กระโดดจนเลยจุดที่มันเจอกัน
  4. คำตอบคือ ( parent ) ของโหนดสุดท้ายที่หยุดหลังการกระโดด

ข้อมูลเพิ่มเติม: https://cses.fi/book/book.pdf (Chapter 18.3)

โจทย์ 4: Distance Queries

"จงหาจำนวนเส้นเชื่อมระหว่างโหนด ( u ) และ ( v ) ใดๆ ในต้นไม้ (Unweighted)"

ต้นไม้มี ( 2 \cdot 10^5 ) โหนด และมีคำถาม ( 2 \cdot 10^5 ) ข้อ

**คำใบ้**: ระยะทางจากโหนดหนึ่งไปอีกโหนดหนึ่งต้องผ่าน LCA เสมอ

สูตรการคำนวณระยะทางบนต้นไม้

dist(a, b) = depth(a) + depth(b) - 2 \cdot depth(LCA(a, b))

1. หาความลึก ( depth ) ของทุกโหนดด้วย DFS เพียงครั้งเดียวในขั้นตอน Preprocessing

2. หา LCA ของโหนด ( a ) และ ( b ) ด้วยเทคนิค Binary Lifting ในเวลา ( O(\log n) )

3. แทนค่าในสูตรเพื่อรับคำตอบในเวลา ( O(1) ) หลังได้ LCA

รายละเอียด: https://cses.fi/book/book.pdf (Chapter 18.3)

ลงมือแก้โจทย์จริง!

CSES Problem Set

- Tree Diameter
- Tree Distances I & II
- Company Queries I & II
- Distance Queries

AtCoder Educational DP

- Problem P: Independent Set
- Problem U: Grouping
(สำหรับฝึกฝน Tree DP ขั้นสูง)

Coding Time: 15.00 - 17.00