Tree Traversal Applications
การประยุกต์ใช้ BFS และ DFS ในปัญหาต้นไม้

Day 06 Afternoon: จากการท่องโหนดพื้นฐานสู่การคำนวณคุณสมบัติเชิงลึก

หัวข้อการบรรยายช่วงบ่าย

DFS Applications

การหาขนาด Subtree, ความสูง และ Dynamic Programming บนต้นไม้

BFS & Distance

การหาระยะทางที่สั้นที่สุดและลำดับเลเยอร์ (Level-order)

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

ทำไมการท่องไปใน Tree ถึงง่ายกว่า Graph ทั่วไป?

1

**ไม่มีวงจร (No Cycles)**: เราไม่จำเป็นต้องกังวลว่าจะวนกลับมาที่เดิมผ่านเส้นทางอื่น ทำให้การจัดการสถานะ `visited` ง่ายขึ้น

2

**เส้นทางเดียว (Unique Path)**: มีเพียงเส้นทางเดียวที่เชื่อมระหว่าง 2 โหนดใดๆ เสมอ

3

**โครงสร้างเรียกซ้ำ (Recursive)**: ต้นไม้มีคุณสมบัติ Self-similarity ซึ่งเหมาะมากกับการใช้ DFS ร่วมกับสมการเวียนเกิด

อ่านเพิ่มเติม: https://roadmap.sh/datastructures-and-algorithms

การหาขนาดของต้นไม้ย่อย (Subtree Size)

โจทย์: ในโหนด $ s $ ใดๆ มีโหนดอยู่ภายใต้โหนดนี้ทั้งหมดกี่โหนด?

เราใช้ DFS ในการคำนวณโดยอาศัยแนวคิด **Post-order**:
$ count(s) = 1 + \sum_{u \in children(s)} count(u) $

void dfs(int s, int e) {
  count[s] = 1;
  for (auto u : adj[s]) {
    if (u == e) continue;
    dfs(u, s);
    count[s] += count[u];
  }
}

อ้างอิงอัลกอริทึม: https://cses.fi/book/book.pdf (Chapter 14)

ตัวอย่างโจทย์และการรับข้อมูล

โครงสร้างต้นไม้ (ตัวอย่าง):

ให้ 1 เป็น Root โดยมีเส้นเชื่อมดังนี้
1-2, 1-3, 1-4, 1-5, 2-6, 4-7, 4-8, 4-9

Sample Input:
8
1 2
1 3
1 4
1 5
2 6
4 7
4 8
4 9

ผลลัพธ์ที่ต้องการ:

ขนาด subtree ของโหนดต่างๆ (count[s])

Sample Output:
โหนด 4: ขนาด = 4 (มี 4,7,8,9)
โหนด 2: ขนาด = 2 (มี 2,6)
โหนด 1: ขนาด = 9 (โหนดทั้งหมด)

ขั้นตอนการคำนวณ (Step-by-Step)

1

เริ่มต้นที่โหนดใบ (Leaf Nodes) อัลกอริทึมจะลงไปลึกที่สุดจนเจอโหนดที่ไม่มีลูก (เช่น 6, 3, 7, 8, 9) และกำหนดให้ count[leaf] = 1

2

**Recursive Step:** เมื่อกลับขึ้นมาจากโหนดลูก (Post-order) โหนดพ่อจะบวกขนาดของโหนดลูกเข้าไปในตัวเอง
เช่น โหนด 4 มีลูกคือ 7, 8, 9 ซึ่งแต่ละโหนดมีขนาด 1 ดังนี้
count[6] = 1 (ตัวเอง) + count[7] + count[8] + count[9]
count[6] = 1 + 1 + 1 + 1 = 4

3

**การหา Root:** ทำซ้ำจนถึงโหนด 1
count[10] = 1 + count[11] + count[12] + count[6] + count[13]
count[10] = 1 + 2 + 1 + 4 + 1 = 9

โจทย์ประยุกต์: การนับค่าใน Subtree

โจทย์: จงนับจำนวนโหนดที่มีค่าเท่ากับ $ x $ ภายใน Subtree ของ $ s $

แนวทางแก้ปัญหา (Offline Algorithm)

ใช้ DFS ท่องไปในต้นไม้และใช้ Map Data Structure เก็บความถี่ของค่าในแต่ละโหนด
เมื่ออยู่ที่โหนด $ s $ ให้รวม Map จากโหนดลูกทุกตัวเข้าด้วยกัน (Merging Data Structures)
เราสามารถตอบคำถามของโหนด $ s $ ได้ทันทีหลังจากที่รวม Map ของลูกๆ เสร็จแล้ว
**Optimization:** หากต้องการความเร็วสูงขึ้น สามารถใช้เทคนิค "Small to Large Merging" เพื่อให้ได้ Time Complexity $ O(n \log^2 n) $ หรือ $ O(n \log n) $

อ้างอิงเทคนิค: Chapter 18.4 (Offline Algorithms)

การหาระยะทางและความลึก

Depth (จากบนลงล่าง)

ส่งค่า $ depth + 1 $ ลงไปพร้อมกับการเรียกฟังก์ชันลูก เพื่อระบุระดับของโหนด

Height (จากล่างขึ้นบน)

$ height(s) = \max(height(u)) + 1 $
เมื่อลูกๆ ส่งคำตอบที่สูงที่สุดกลับขึ้นมาหาพ่อ

dist(root, v) = depth[v]

โจทย์: การหาเส้นผ่านศูนย์กลาง (Tree Diameter)

นิยาม: ระยะทางที่ไกลที่สุดระหว่างโหนดสองโหนดใดๆ ในต้นไม้

ตัวอย่าง Input:

7 โหนด, เส้นเชื่อม:
1-2, 1-3, 1-4, 2-5, 2-6, 4-7

ตัวอย่าง Output:

เส้นผ่านศูนย์กลาง = 4
(เช่น ระยะทางจาก 5 ถึง 7)

แนวทางการแก้ปัญหาด้วย Two-DFS Algorithm:

เลือกโหนดเริ่มต้น $ a $ ใดๆ แล้วหาโหนด $ b $ ที่อยู่ **ไกลที่สุด** จาก $ a $
จากโหนด $ b $ ให้หาโหนด $ c $ ที่อยู่ **ไกลที่สุด** จาก $ b $
ระยะทางระหว่าง $ b $ และ $ c $ คือคำตอบ (Diameter)

อ้างอิง: Competitive Programmer's Handbook (Chapter 14.2)

การประยุกต์ใช้ DFS เพื่อหาระยะทางไกลสุด

Diameter Algorithm (C++)

Time Complexity: $ O(n) $

// ใช้ DFS เพื่อเก็บระยะทาง (dist) ของทุกโหนดจากจุดเริ่ม s
void dfs(int s, int e, int d) {
  dist[s] = d;
  for (auto u : adj[s]) {
    if (u != e) dfs(u, s, d + 1);
  }
}

// ในฟังก์ชัน main:
dfs(1, 0, 0); // 1. หาโหนด b ที่ไกลจากโหนด 1
// (เลือกโหนด b ที่มี dist[b] สูงสุด)
dfs(b, 0, 0); // 2. หาโหนด c ที่ไกลจากโหนด b
// คำตอบคือค่า dist[c] ที่ได้จากการ DFS รอบสอง

**ทำไมถึงใช้ได้?** โหนดที่ไกลที่สุดจากโหนดใดๆ มักจะเป็นจุดปลายจุดหนึ่งของเส้นผ่านศูนย์กลางเสมอ ดังนั้นการหาจุดที่ไกลที่สุดสองครั้งจึงการันตีการเจอเส้นทางที่ยาวที่สุดในต้นไม้

พื้นฐาน Dynamic Programming บนต้นไม้

"Tree DP คือการทำ DFS ที่มีการจดจำผลลัพธ์"

เรามักจะคำนวณค่าสถานะ (State) ของโหนดพ่อ โดยอิงจากค่าสถานะของโหนดลูก (Children states) ซึ่งทำได้โดยการใช้ DFS ท่องโหนดไปจนถึงใบ (Leaf) แล้วนำผลลัพธ์สะสมขึ้นมาเรื่อยๆ

ตัวอย่างปัญหา:

• การหาค่ารวมสูงสุดใน Subtree
• การหาเส้นทางที่ยาวที่สุดที่ผ่านโหนดนั้นๆ
• การเลือกเซตของโหนดที่ไม่ติดกันให้ได้มูลค่าสูงสุด (Independent Set)

รายละเอียดเพิ่มเติม: https://atcoder.jp/contests/dp

โจทย์: เซตอิสระที่ใหญ่ที่สุด (Maximum Independent Set)

โจทย์: จงเลือกโหนดจำนวนมากที่สุดในต้นไม้ โดยห้ามเลือกโหนดที่ติดกัน (มีเส้นเชื่อมถึงกัน)

แนวคิดการแบ่งสถานะ (States):

เรากำหนดสถานะให้แต่ละโหนด $ v $ สองแบบ :

$ dp[v][4] $: ขนาด MIS ใน subtree ของ $ v $ เมื่อ **เลือก** โหนด $ v $
$ dp[v] $: ขนาด MIS ใน subtree ของ $ v $ เมื่อ **ไม่เลือก** โหนด $ v $

สูตรความสัมพันธ์ (Transitions) :

ถ้าเลือก $ v $: ลูกทุกตัว $ w $ ของมัน **ต้องไม่ถูกเลือก**
$ dp[v][4] = 1 + \sum dp[w] $
ถ้าไม่เลือก $ v $: ลูกแต่ละตัว $ w $ จะถูก **เลือกหรือไม่ก็ได้** (เอาค่าที่มากที่สุด)
$ dp[v] = \sum \max(dp[w][4], dp[w]) $

อ้างอิงอัลกอริทึม: Dynamic Programming on Trees (Chapter 14 )

C++ Implementation for Tree DP

Maximum Independent Set on Tree

Time Complexity: $ O(n) $

int dp[N][5];
void solve(int s, int e) {
  dp[s][4] = 1; // กรณีเลือกตัวเอง
  dp[s] = 0; // กรณีไม่เลือกตัวเอง

  for (auto u : adj[s]) {
    if (u == e) continue;
    solve(u, s); // ท่องลงไปจนถึงโหนดใบ (Post-order )

    // คำนวณค่าสะสมกลับขึ้นมาหาพ่อ
    dp[s][4] += dp[u];
    dp[s] += max(dp[u][4], dp[u]);
  }
}

💡 ผลลัพธ์สุดท้าย:
หลังจากเรียก `solve(root, 0)` คำตอบที่ได้คือ `max(dp[root], dp[root][4])`

BFS: ระยะทางสั้นที่สุดและเลเยอร์

BFS

Breadth-First Search เหมาะมากสำหรับการหา **ระยะทางที่สั้นที่สุด (Shortest Path)** จาก Root ไปยังโหนดอื่นๆ ในต้นไม้ที่ไม่มีน้ำหนักเส้นเชื่อม (Unweighted Tree)

เยี่ยมชมโหนดทีละชั้น (Level-order)
โหนดที่ถูกพบก่อนในเลเยอร์ที่ต่ำกว่าจะมีระยะทางใกล้ Root กว่าเสมอ
ใช้ Queue ในการควบคุมลำดับการเยี่ยมชม

แหล่งเรียนรู้: https://www.geeksforgeeks.org/tree-traversals-bfs-and-dfs/

โจทย์: ระยะห่างจากโหนดเริ่ม (Tree Distance)

โจทย์: จงหาระยะทางสั้นที่สุดจาก Root (โหนด 1) ไปยังทุกโหนดในต้นไม้

แนวทางแก้ปัญหาด้วย BFS:

Queue: ใช้เก็บโหนดที่กำลังจะเข้าไปเยี่ยมชมตามลำดับความใกล้-ไกล
Distance Array: ใช้เก็บระยะทางจาก Root (ให้ `dist[root] = 0` และโหนดอื่นเป็นค่าว่าง)
Layer Processing: เมื่อดึงโหนด $ s $ ออกจาก Queue ให้ตรวจดูโหนดเพื่อนบ้าน $ u $ ถ้ายังไม่เคยไป ให้ตั้งค่า `dist[u] = dist[s] + 1` แล้วใส่ $ u $ ลงใน Queue
Efficiency: วิธีนี้การันตีว่าจะได้ระยะทางที่สั้นที่สุดเสมอในต้นไม้ที่ไม่มีน้ำหนัก (Unweighted Tree)

อ้างอิง: Competitive Programmer's Handbook (Chapter 12.2)

C++ Implementation for Tree BFS

// ใช้ Queue ในการหา Shortest Path บนต้นไม้

Time: $ O(V + E) $

#include <queue>
void bfs(int x) {
  visited[x] = true;
  dist[x] = 0;
  queue<int> q;
  q.push(x);

  while (!q.empty()) {
    int s = q.front(); q.pop();
    // เยี่ยมชมโหนดลูกทุกตัว
    for (auto u : adj[s]) {
      if (visited[u]) continue;
      visited[u] = true;
      dist[u] = dist[s] + 1;
      q.push(u);
    }
  }
}

💡

การทำงานของ BFS จะกระจายออกเป็นวงกว้าง (Breadth) ทำให้เราสามารถระบุ "ความลึก" (Depth) หรือ "ระดับ" (Level) ของโหนดในต้นไม้ได้อย่างแม่นยำ

ปัญหาเส้นผ่านศูนย์กลาง (Tree Diameter)

นิยาม: ระยะทางที่ยาวที่สุดระหว่างโหนด 2 โหนดใดๆ ในต้นไม้

หนึ่งในวิธีการหา Diameter ที่มีประสิทธิภาพและนิยมใช้ที่สุดคือการทำ **DFS/BFS 2 ครั้ง** ซึ่งจะให้ความซับซ้อนของเวลาเพียง $ O(n) $

"Diameter มักเป็นองค์ประกอบสำคัญในโจทย์กราฟระดับโอลิมปิก"

ตัวอย่างโจทย์: ระยะทางไกลสุดในเครือข่าย

โจทย์: กำหนดต้นไม้ที่มี $ n $ โหนด จงหาความยาวของเส้นทางที่ยาวที่สุด

ขั้นตอนที่ 1: หาจุดปลายด้านที่หนึ่ง

เลือกโหนด $ a $ ใดก็ได้ (เช่น โหนด 1) แล้วใช้ DFS เพื่อหาโหนด $ b $ ที่อยู่ ไกลที่สุด จาก $ a $

ขั้นตอนที่ 2: หาจุดปลายด้านที่สอง

เริ่ม DFS จากโหนด $ b $ ที่เจอ เพื่อหาโหนด $ c $ ที่อยู่ ไกลที่สุด จาก $ b $ ระยะทางนี้คือ Diameter

"โหนดที่อยู่ไกลที่สุดจากโหนดใดๆ มักจะเป็นจุดปลายจุดหนึ่งของ Diameter เสมอ"

C++ Solution: Tree Diameter (Two-DFS)

int maxDist = -1, farthestNode;
void dfs(int s, int e, int d) {
  if (d > maxDist) { maxDist = d; farthestNode = s; }
  for (auto u : adj[s]) {
    if (u != e) dfs(u, s, d + 1);
  }
}

// การเรียกใช้งานใน main()
maxDist = -1; dfs(1, 0, 0); // รอบที่ 1: หาจุดปลาย b
int node_b = farthestNode;
maxDist = -1; dfs(node_b, 0, 0); // รอบที่ 2: หาจุดปลาย c จาก b
cout << "Diameter: " << maxDist << endl;

Time Complexity: $ O(n) $

Space Complexity: $ O(n) $ (Adjacency List)

อ้างอิง: Competitive Programmer's Handbook (Chapter 14.2)

อัลกอริทึม 2-DFS เพื่อหา Diameter

Step 1:

เริ่มจากโหนดใดก็ได้ (โหนด $ x $) แล้วใช้ DFS หาโหนดที่อยู่ไกลที่สุดจากมัน (สมมติว่าเป็นโหนด $ a $)

Step 2:

เริ่มจากโหนด $ a $ แล้วใช้ DFS หาโหนดที่ไกลที่สุดจาก $ a $ อีกครั้ง (สมมติว่าเป็นโหนด $ b $)

ระยะทางระหว่าง $ a $ และ $ b $ คือ Diameter!

ทำไมถึงใช้ได้?
เพราะจุดปลายของ Diameter จะเป็นจุดที่อยู่ไกลที่สุดจากโหนดใดๆ ในต้นไม้เสมอ การทำ DFS ครั้งแรกจึงรับประกันว่าเราจะเจอ "จุดปลาย" ด้านหนึ่งแน่นอน

อ้างอิง: https://cses.fi/book/book.pdf

โจทย์: เครือข่ายที่ยาวที่สุด

ปัญหา: จงหาความยาวของเส้นทางที่ยาวที่สุดในต้นไม้ (Diameter)

ตัวอย่าง Input:

n = 6 (จำนวนโหนด)
เส้นเชื่อม: (1,2), (2,3), (2,4), (4,5), (4,6)

อธิบายการคำนวณ:

เส้นทาง 3-2-4-5 มีความยาว 3
เส้นทาง 3-2-4-6 มีความยาว 3
Diameter = 3

หมายเหตุ: ในต้นไม้ที่ไม่มีน้ำหนัก (Unweighted) ความยาวเส้นทางคือนับตามจำนวนเส้นเชื่อม

กลยุทธ์การเขียนโปรแกรม 2-DFS

เพื่อให้โค้ดมีประสิทธิภาพ $ O(n) $ เราจะใช้โครงสร้าง DFS แบบไม่ใช้ `visited` array:

1

DFS Function: รับพารามิเตอร์ `(node, parent, distance)` เพื่อท่องไปในต้นไม้โดยไม่ย้อนกลับทางเดิม

2

Tracking: ใช้ตัวแปร Global เก็บ `maxDist` และ `farthestNode` โดยจะอัปเดตค่าทุกครั้งที่เจอระยะทางที่ไกลกว่าเดิม

3

Main Execution: เรียก DFS ครั้งแรกเพื่อหาจุดปลายหนึ่งด้าน จากนั้นใช้จุดนั้นเป็นจุดเริ่มในการเรียก DFS ครั้งที่สองเพื่อหาค่า Diameter จริง

C++ Solution for Tree Diameter

// Chapter 14.2: Diameter using 2-DFS

int maxD = -1, node_a;
vector<int> adj[N];

void dfs(int s, int e, int d) {
  if (d > maxD) { maxD = d; node_a = s; } // จำโหนดที่ไกลที่สุด
  for (auto u : adj[s]) {
    if (u != e) dfs(u, s, d + 1); // ป้องกันการวิ่งกลับไปหา Parent
  }
}

int main() {
  // ... รับ Input เส้นเชื่อมใส่ adj ...
  maxD = -1; dfs(1, 0, 0); // รอบที่ 1: หาโหนด b จากจุดสุ่ม
  int b = node_a;
  maxD = -1; dfs(b, 0, 0); // รอบที่ 2: เริ่มจาก b หาจุด c ที่ไกลสุด
  cout << "Diameter: " << maxD << endl; // maxD ตอนนี้คือคำตอบ
}

⏱️ Time Complexity: $ O(n) $

💾 Space Complexity: $ O(n) $

อ้างอิงโค้ดพื้นฐาน: Competitive Programmer's Handbook

การสืบค้นบรรพบุรุษ (Ancestors)

การใช้ DFS ช่วยให้เราประมวลผลความสัมพันธ์ระหว่างโหนดได้:

K
**K-th Ancestor**: โหนดที่อยู่สูงขึ้นไป $ k $ ระดับจากโหนดปัจจุบัน (แก้ด้วย Binary Lifting)
L
**Lowest Common Ancestor (LCA)**: บรรพบุรุษร่วมที่ต่ำที่สุดของโหนด $ u $ และ $ v $

"การคำนวณเหล่านี้ต้องอาศัยการเก็บข้อมูลระหว่างการทำ DFS (Preprocessing)"

เพิ่มเติมเรื่อง LCA: https://usaco.guide/gold/LCA

โจทย์: ใครคือบรรพบุรุษของฉัน?

โจทย์: กำหนดต้นไม้ที่มี $ n $ โหนด จงตอบคำถาม $ q $ ครั้ง ว่าบรรพบุรุษลำดับที่ $ k $ ของโหนด $ x $ คือใคร?

ตัวอย่าง Input:

โหนด: 8, Root: 1
เส้นเชื่อม: (1,2), (1,4), (1,5), (2,6), (4,3), (4,7), (7,8)
Query: บรรพบุรุษลำดับที่ 2 ของโหนด 8 คือ?

ลำดับการไล่สายสัมพันธ์:

1. โหนด 8 มีพ่อ (ลำดับที่ 1) คือ 7
2. โหนด 7 มีพ่อ (ลำดับที่ 2) คือ 4
คำตอบคือ โหนด 4

*หากใช้การขยับทีละขั้น (Naive) จะใช้เวลา $ O(n) $ ต่อ Query ซึ่งจะช้าเกินไปถ้าต้นไม้เป็นเส้นตรงและมี Query จำนวนมาก

กลยุทธ์: Binary Lifting

แนวคิด: ขยับเป็นระยะทางกำลังของ 2 เพื่อลดเวลาเป็น $ O(\log n) $

1. Preprocessing: สร้างตาราง `up[x][i]` ซึ่งหมายถึงบรรพบุรุษลำดับที่ $ 2^i $ ของโหนด $ x $
สูตร: $ up[x][i] = up[up[x][i-1]][i-1] $ (บรรพบุรุษที่ $ 2^i $ คือบรรพบุรุษที่ $ 2^{i-1} $ ของโหนดที่สูงขึ้นไป $ 2^{i-1} $ อีกที)

2. Query: แตกค่า $ k $ เป็นผลรวมของกำลังเลข 2 (Binary Representation)
เช่น ถ้าหาลำดับที่ 11 ($ 8+2+1 $): ให้ขยับโหนดไปที่บรรพบุรุษลำดับที่ 8 -> 2 -> 1 ตามลำดับ

Preprocessing ใช้เวลา $ O(n \log n) $ และตอบ Query ใน $ O(\log n) $

C++ Solution: K-th Ancestor

int up[N][LOG]; // up[node][power_of_2]

// 1. สร้างตารางระหว่างการทำ DFS
void dfs(int s, int e) {
  up[s] = e;
  for (int i = 1; i < LOG; i++)
    up[s][i] = up[up[s][i-1]][i-1];

  for (auto u : adj[s])
    if (u != e) dfs(u, s);
}

// 2. ฟังก์ชันตอบ Query
int get_ancestor(int x, int k) {
  for (int i = 0; i < LOG; i++)
    if ((k >> i) & 1) x = up[x][i]; // ถ้าบิตที่ i เป็น 1 ให้ยกตัวขึ้น 2^i ชั้น
  return x == 0 ? -1 : x; // คืนค่าโหนดบรรพบุรุษ
}

Precompute: $ O(n \log n) $

Query: $ O(\log k) $

บรรพบุรุษร่วมที่ต่ำที่สุด (Naive LCA)

แนวคิดการหา LCA แบบพื้นฐานด้วย Traversal:

ใช้อาเรย์ parent[v] และ depth[v] ที่ได้จาก DFS
ปรับโหนดทั้งสองให้อยู่ในระดับความลึก (Depth) เดียวกันโดยการเดินขึ้น
จากนั้นขยับโหนดทั้งสองขึ้นไปพร้อมๆ กันทีละระดับจนกว่าจะเจอกัน

"วิธีนี้ใช้เวลา ( O(n) ) ในกรณีเลวร้ายที่สุด (เช่น Tree ที่เป็นเส้นตรง) ซึ่งอาจไม่เพียงพอในบางโจทย์"

ศึกษาเพิ่มเติม: https://cses.fi/book/book.pdf (Chapter 15.3)

LCA: กลยุทธ์ Binary Lifting

นิยาม: โหนดที่ต่ำที่สุดที่เป็นบรรพบุรุษของทั้งสองโหนด .

ขั้นตอนการหาคำตอบ (Method 1):

ใช้ข้อมูลจาก Binary Lifting (ตาราง up[x][i]) เพื่อช่วยในการกระโดดขึ้นไปหาบรรพบุรุษ .
ปรับระดับ (Equalize Depth): หากโหนดทั้งสองลึกไม่เท่ากัน ให้ขยับโหนดที่ลึกกว่าขึ้นมาให้อยู่ระดับเดียวกับอีกโหนดหนึ่ง .
ก้าวร่วมกัน (Simultaneous Jump): ขยับทั้งสองโหนดขึ้นไปพร้อมกันด้วยระยะทางที่มากที่สุดเท่าที่เป็นไปได้ แต่ต้องไม่ข้ามจุดที่พวกมันเจอกัน .
สรุปผล: เมื่อขยับต่อไม่ได้แล้ว พ่อของโหนดปัจจุบันก็คือ Lowest Common Ancestor .

ประสิทธิภาพ: การประมวลผลล่วงหน้าใช้ $O(n \log n)$ และตอบแต่ละ Query ได้ใน $O(\log n)$ .

C++ Solution: Binary Lifting LCA

int get_lca(int a, int b) {
  if (depth[a] < depth[b]) swap(a, b); // ให้ a ลึกกว่าเสมอ

  // 1. ปรับ a ให้สูงขึ้นมาเท่ากับระดับของ b
  for (int i = LOG - 1; i >= 0; i--) {
    if (depth[a] - (1 << i) >= depth[b]) a = up[a][i];
  }

  if (a == b) return a; // ถ้า b เป็นบรรพบุรุษของ a อยู่แล้ว

  // 2. กระโดดขึ้นพร้อมกันทีละระดับกำลัง 2
  for (int i = LOG - 1; i >= 0; i--) {
    if (up[a][i] != up[b][i]) { a = up[a][i]; b = up[b][i]; }
  }
  return up[a]; // LCA คือพ่อของโหนดปัจจุบัน
}

ตัวอย่างการใช้งาน:

โหนด 5 อยู่ระดับ 3, โหนด 8 อยู่ระดับ 4 .
LCA ของ 5 และ 8 คือ 2 ซึ่งอยู่ระดับ 2 .

การนำไปใช้ต่อ:

เราสามารถใช้ LCA เพื่อหา ระยะทาง (Distance) ระหว่างโหนด $a$ และ $b$ ได้โดยใช้สูตร:
$depth(a) + depth(b) - 2 \cdot depth(LCA(a,b))$ .

Binary Lifting: ยกระดับความเร็วในการหา Ancestor

แทนที่จะเดินขึ้นทีละ 1 ขั้น เราจะเดินขึ้นทีละ ( 2^k ) ขั้น:

up[v][k] // คือบรรพบุรุษลำดับที่ ( 2^k ) ของโหนด v

การเตรียมข้อมูล (Preprocessing) ใช้เวลา ( O(n \log n) ) ผ่าน DFS ครั้งเดียว แต่ช่วยให้เราหา LCA ได้ในเวลาเพียง ( O(\log n) ) ต่อหนึ่งคำถาม (Query)

รายละเอียดอัลกอริทึม: https://usaco.guide/gold/LCA

โจทย์: บรรพบุรุษร่วมที่ต่ำที่สุด (LCA)

นิยาม: โหนด $c$ ที่เป็นบรรพบุรุษของทั้ง $a$ และ $b$ โดยที่ $c$ อยู่ในระดับที่ลึกที่สุด

ตัวอย่างโครงสร้าง:

โหนด 1 เป็น Root
1 -> 2, 3, 4
2 -> 5, 6
4 -> 7
6 -> 8

Queries:

• LCA(5, 8): คำตอบคือ โหนด 2
• LCA(5, 7): คำตอบคือ โหนด 1
• LCA(2, 8): คำตอบคือ โหนด 2

*โจทย์ต้องการให้ตอบคำถามเหล่านี้หลายๆ ครั้ง (Queries) ในเวลาที่รวดเร็วที่สุด

อัลกอริทึม LCA (Method 1)

แบ่งการทำงานเป็น 2 ส่วนหลัก :

1

ปรับระดับโหนดให้เท่ากัน (Level Alignment)

หาก $depth(a) \neq depth(b)$ ให้ขยับโหนดที่ลึกกว่าขึ้นมาจนอยู่ในระดับเดียวกัน โดยใช้ตาราง up[v][k]

2

กระโดดขึ้นพร้อมกัน (Simultaneous Binary Jump)

ขยับทั้งสองโหนดขึ้นไปด้วยระยะทาง $2^k$ ที่มากที่สุด แต่ต้องทำให้โหนดทั้งสอง ยังไม่บรรจบกัน เมื่อขยับต่อไม่ได้แล้ว พ่อของพวกมันคือ LCA

ประสิทธิภาพ: ตอบแต่ละคำถามได้ใน $O(\log n)$ หลังจากการเตรียมข้อมูล $O(n \log n)$

C++ Implementation: get_lca

int get_lca(int a, int b) {
  if (depth[a] < depth[b]) swap(a, b);

  // 1. ยกโหนด a ขึ้นมาให้ระดับเดียวกับ b
  for (int i = LOG - 1; i >= 0; i--) {
    if (depth[a] - (1 << i) >= depth[b]) a = up[a][i];
  }

  if (a == b) return a;

  // 2. กระโดดขึ้นพร้อมกันด้วยระยะทางที่มากที่สุดเท่าที่บรรพบุรุษยังไม่ซ้ำกัน
  for (int i = LOG - 1; i >= 0; i--) {
    if (up[a][i] != up[b][i]) {
      a = up[a][i]; b = up[b][i];
    }
  }
  return up[a]; // คืนค่าพ่อของโหนดปัจจุบันซึ่งคือ LCA
}

💡 Tip: ใช้ up[v] เพื่อเก็บโหนดพ่อจากการทำ DFS

🎯 Application: ระยะทางระหว่าง $a, b = depth(a) + depth(b) - 2 \cdot depth(LCA)$

การหาระยะทางระหว่างโหนดใดๆ

สูตรการคํานวณระยะทางระหว่างโหนด u และ v:

dist(u, v) = depth[u] + depth[v] - 2 \cdot depth[LCA(u, v)]

หลักการ: เราบวกระยะทางจากโหนดทั้งสองไปยัง Root แล้วลบส่วนของเส้นทางที่ซ้ำกันออก (เส้นทางจาก Root ไปยัง LCA) ซึ่งช่วยให้เราหาระยะทางได้ใน ( O(\log n) ) ทันทีหลังจากทำ Preprocessing

โจทย์: ระยะทางที่สั้นที่สุดระหว่างเพื่อนบ้าน

โจทย์: กำหนดต้นไม้ที่มี $ n $ โหนด จงหาระยะทางสั้นที่สุดระหว่างโหนด $ u $ และ $ v $

ตัวอย่างโครงสร้าง:

โหนด 2 อยู่ระดับ (Depth) 2
โหนด 5 อยู่ระดับ 3
โหนด 8 อยู่ระดับ 4
LCA(5, 8) คือ โหนด 2

การคำนวณ:

3 + 4 - 2(2) = 3

ระยะทางระหว่าง 5 และ 8 คือ 3

อ้างอิงหลักการ: ระยะทางระหว่างโหนด $ a $ และ $ b $ ลดรูปได้จากการหา Lowest Common Ancestor

แนวทางการเขียนโปรแกรม

กระบวนการประมวลผล (Algorithm Steps):

1

DFS Preprocessing: ท่องต้นไม้หนึ่งรอบเพื่อเก็บค่า depth[s] ของทุกโหนด และสร้างตาราง Binary Lifting สำหรับหา LCA

2

LCA Function: สร้างฟังก์ชัน get_lca(u, v) ที่ใช้เวลา $ O(\log n) $ ในการหาบรรพบุรุษร่วมที่ต่ำที่สุด

3

Distance Calculation: ใช้ฟังก์ชันหลักคำนวณตามสูตร:
depth[u] + depth[v] - 2 * depth[get_lca(u, v)]

C++ Solution: Path Distance

// สูตรคำนวณระยะทางจาก Competitive Programmer's Handbook
int get_distance(int u, int v) {
  int lca = get_lca(u, v); // เรียกใช้ฟังก์ชันหา LCA ที่สร้างไว้
  return depth[u] + depth[v] - 2 * depth[lca];
}

int main() {
  // หลังทำ DFS และ Preprocessing เสร็จแล้ว
  int u = 5, v = 8;
  cout << "Distance between " << u << " and " << v << ": ";
  cout << get_distance(u, v) << endl;
  return 0;
}

⏱️ Complexity: O(log N) ต่อ Query

📌 ประยุกต์ใช้ได้ในโจทย์: Tree Path Sum Queries

อ้างอิงข้อมูล: Competitive Programmer's Handbook (Chapter 18.3)

Tree DP: การหาผลรวมในต้นไม้ย่อย

หากแต่ละโหนดมีค่า ( value[s] ) เราต้องการหา ( sum[s] ) ซึ่งคือผลรวมของโหนดทั้งหมดใน Subtree ของ s

void dfs(int s, int e) {
  sum[s] = value[s];
  for (auto u : adj[s]) {
    if (u == e) continue;
    dfs(u, s);
    sum[s] += sum[u];
  }
}

จุดประสงค์:

ใช้ในการแก้โจทย์ที่ต้องพิจารณาทรัพยากรภายใน Subtree หรือการแบ่งงานในโครงสร้างองค์กร

โจทย์: งบประมาณรวมของแผนก

โจทย์: กำหนดโครงสร้างบริษัทเป็นต้นไม้ โดยแต่ละโหนดมีค่า "งบประมาณรายบุคคล" จงหา "งบประมาณรวม" ของทุก Subtree

ตัวอย่าง Input:

โหนด: 5 (1 เป็น Root)
ค่า (Value): {1:10, 2:5, 3:2, 4:1, 5:1}
เส้นเชื่อม: (1,2), (1,3), (2,4), (2,5)

ผลลัพธ์ที่ต้องการ (Output):

sum[4] = 1, sum[5] = 1
sum[6] = 5 + 1 + 1 = 7
sum[7] = 2
sum[8] = 10 + 7 + 2 = 19

การคำนวณต้องทำจาก "โหนดใบ" ขึ้นไปหา "โหนดพ่อ" (Bottom-up) เพื่อให้ข้อมูลพร้อมใช้งาน

แนวทางการเขียนโปรแกรม

กลยุทธ์การประมวลผล (Strategy):

1

Recursive DFS: เริ่มต้นการทำงานจาก Root และปล่อยให้ Recursion เดินลงไปจนถึงโหนดที่ลึกที่สุด (Leaf)

2

Base Initialization: ที่แต่ละโหนด $s$ ให้ตั้งต้นค่า sum[s] เท่ากับค่าของตัวเอง value[s]

3

Post-order Accumulation: เมื่อกลับขึ้นมาจากฟังก์ชันลูก (Recursive Call) ให้นำผลรวมของลูกแต่ละตัวมาบวกสะสมเข้ากับโหนดปัจจุบัน

C++ Solution: Subtree Sum DP

long long sum[N];
int value[N];
vector<int> adj[N];

void dfs_sum(int s, int e) {
  sum[s] = value[s]; // 1. กำหนดค่าเริ่มต้นของตัวเอง
  for (auto u : adj[s]) {
    if (u == e) continue;
    dfs_sum(u, s); // 2. ท่องลงไปใน Subtree ของลูก
    sum[s] += sum[u]; // 3. นำคำตอบที่คำนวณเสร็จแล้วมาบวกคืนให้พ่อ
  }
}

int main() {
  // Precompute all sums starting from root 1
  dfs_sum(1, 0);
  cout << "Total sum of root: " << sum[8] << endl;
}

⏱️ Complexity: O(n) เพราะเยี่ยมชมโหนดละ 1 ครั้ง

⚠️ ระวัง: หากจำนวนโหนดมาก ให้ระวัง Stack Overflow จาก Recursion

อ้างอิงหลักการ: Chapter 14 Dynamic Programming on Trees

การหา Diameter ด้วยแนวคิด DP

นอกจากวิธี 2-DFS เรายังสามารถใช้ DP เพื่อหา Diameter ในโจทย์ที่ซับซ้อนกว่าได้:

f(v):

ระยะทางที่ยาวที่สุดจากโหนด v ลงไปหา Leaf ใน Subtree ของมัน

g(v):

Diameter ของเส้นทางที่ยาวที่สุดที่ ผ่าน โหนด v

g(v) = (ค่า f ที่ใหญ่ที่สุด 2 อันดับแรกของลูกๆ) + 2

อ้างอิงอัลกอริทึม: https://cses.fi/book/book.pdf (Chapter 14.3)

โจทย์: เส้นทางที่ยาวที่สุดในเครือข่าย

โจทย์: จงหาความยาวของเส้นทางที่ยาวที่สุดในต้นไม้ โดยห้ามใช้การ DFS 2 รอบ (ให้ใช้ DP)

แนวคิดการแบ่งปัญหา:

ในต้นไม้ที่ถูก Root ไว้แล้ว ทุกเส้นทางจะมี "จุดสูงสุด" (Highest Point) เสมอ . เราจะหาเส้นทางที่ยาวที่สุดที่ผ่านแต่ละโหนดในฐานะจุดสูงสุด แล้วหาค่ามากที่สุดจากทั้งหมดนั้น .

ตัวอย่างสถานะที่โหนด $ v $:

ลูกคนที่ 1 มีทางยาวสุดไปใบ = 3
ลูกคนที่ 2 มีทางยาวสุดไปใบ = 2
เส้นทางที่ยาวที่สุดผ่าน $ v $ คือ $ 3 + 2 + 2 = 7 $

กลยุทธ์การประมวลผลสถานะ

การคำนวณ $ f(v) $ และ $ g(v) $ ในรอบเดียว:

1

Compute $ f(v) $: ท่องลงไปหาใบ (Leaf) แล้วส่งระยะทางที่ไกลที่สุดกลับขึ้นมาหาพ่อ โดย $ f(v) = 1 + \max(f(child)) $ .

2

Maintain Top 2: ที่แต่ละโหนด ให้เก็บค่า $ f $ ของลูกที่มากที่สุด 2 อันดับแรก เพื่อนำมาหาเส้นทางที่ยาวที่สุดที่ "หักมุม" ผ่านโหนดนั้น .

3

Update Diameter: ให้ $ g(v) $ คือผลรวมของค่า $ f $ จากลูก 2 คนที่มากที่สุดบวกเพิ่มอีก 2 เส้นเชื่อม ค่า Diameter สุดท้ายคือค่าสูงสุดของ $ g(v) $ ทุกตัว .

C++ Solution: Diameter via DP

int max_diameter = 0;
int solve_dp(int s, int e) {
  int max_f1 = -1, max_f2 = -1; // เก็บค่า f ที่ใหญ่ที่สุด 2 อันดับ
  for (auto u : adj[s]) {
    if (u == e) continue;
    int f_child = solve_dp(u, s);
    if (f_child > max_f1) { max_f2 = max_f1; max_f1 = f_child; }
    else if (f_child > max_f2) { max_f2 = f_child; }
  }

  // อัปเดตค่า g(s) ซึ่งเป็น Diameter ที่มี s เป็นจุดสูงสุด
  max_diameter = max(max_diameter, max_f1 + max_f2 + 2);

  return max_f1 + 1; // คืนค่า f(s) กลับไปให้โหนดพ่อ
}

⏱️ Time Complexity: O(n)

🎯 เหมาะสำหรับโหนดที่มีน้ำหนัก หรือโจทย์ที่ต้องการหา All Longest Paths .

เทคนิคการทำให้ต้นไม้แบน (Euler Tour)

"เปลี่ยนต้นไม้ให้กลายเป็นอาเรย์ (Linearizing a Tree)"

เราใช้ DFS เพื่อบันทึกเวลาที่ เข้า (Entry) และ ออก (Exit) จากแต่ละโหนด ซึ่งทำให้โหนดทุกลูกใน Subtree จะมีเวลาอยู่ในช่วงเดียวกันเสมอในรูปแบบอาเรย์

[tin[v], tout[v]] // ครอบคลุมโหนด v และทายาททั้งหมด

ตัวอย่างโจทย์: Subtree Sum Query

Problem

ให้ต้นไม้ที่มี N โหนด โดยโหนดแต่ละตัวมีค่า value[v]

มี Query 2 แบบ

1 v x → เปลี่ยนค่า value[v] = x 2 v → หาผลรวมค่าของทุกโหนดใน subtree ของ v

ข้อจำกัด: N, Q ≤ 200000

ถ้าใช้ DFS ทุกครั้งจะช้าเกินไป (O(N) ต่อ query)

แนวคิดการแก้ปัญหา

Step 1: Flatten Tree ด้วย Euler Tour

DFS Order Example 1 ├── 2 │ ├── 4 │ └── 5 └── 3 Euler Order: 1 2 4 5 3

Subtree ของโหนด v จะกลายเป็นช่วงในอาเรย์

subtree(v) = [tin[v], tout[v]]

จากนั้นใช้ Segment Tree / Fenwick Tree เพื่อทำ Range Sum Query ได้เร็ว

Update → point update Query → range sum

Complexity: O((N + Q) log N)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

vector<int> g[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;
long long val[MAXN];
long long fenwick[MAXN];
int N,Q;

void dfs(int v, int p){
    tin[v] = ++timer;

    for(int u : g[v]){
        if(u == p) continue;
        dfs(u,v);
    }

    tout[v] = timer;
}

void update(int i, long long delta){
    for(; i <= N; i += i & -i)
        fenwick[i] += delta;
}

long long query(int i){
    long long s = 0;
    for(; i > 0; i -= i & -i)
        s += fenwick[i];
    return s;
}

long long rangeQuery(int l, int r){
    return query(r) - query(l-1);
}

int main(){

    cin >> N >> Q;

    for(int i=1;i<=N;i++)
        cin >> val[i];

    for(int i=0;i> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);

    for(int i=1;i<=N;i++)
        update(tin[i], val[i]);

    while(Q--){

        int type;
        cin >> type;

        if(type == 1){
            int v; long long x;
            cin >> v >> x;

            update(tin[v], x - val[v]);
            val[v] = x;
        }
        else{
            int v;
            cin >> v;

            cout << rangeQuery(tin[v], tout[v]) << "\n";
        }
    }
}

Euler Tour และการทํา Range Queries

ทำไมเทคนิคนี้ถึงทรงพลัง?

การสืบค้น Subtree: เปลี่ยนจากการท่องกราฟเป็นการหาค่าในอาเรย์ช่วง [tin[v], tout[v]]
การอัปเดตค่า: สามารถใช้ Segment Tree หรือ Fenwick Tree ร่วมกับอาเรย์นี้ได้

"นี่คือพื้นฐานของปัญหาเชิงโครงสร้างขั้นสูงที่ออกสอบบ่อยในรอบลึกๆ"

ศึกษาเพิ่มเติม: https://usaco.guide/gold/tree-euler

ตัวอย่างโจทย์: Subtree Add Query

Problem

ให้ต้นไม้ที่มี N โหนด (root = 1) และค่าเริ่มต้น value[v]

มีคำสั่ง Q คำสั่ง

1 v x → เพิ่มค่า x ให้ทุกโหนดใน subtree ของ v 2 v → แสดงค่า value[v]

ข้อจำกัด

1 ≤ N,Q ≤ 200000

ถ้า DFS ทุกครั้งจะใช้เวลา O(NQ) ซึ่งช้าเกินไป

แนวคิดการแก้ปัญหา

Step 1: Flatten Tree ด้วย Euler Tour

DFS Order 1 ├── 2 │ ├── 4 │ └── 5 └── 3 Euler Order 1 2 4 5 3

Subtree ของ v จะกลายเป็นช่วงต่อเนื่อง

subtree(v) = [tin[v], tout[v]]

Step 2: ใช้ Fenwick Tree

• เพิ่มค่า subtree → range update
• Query ค่า node → point query

update(tin[v], +x) update(tout[v]+1, -x)

Complexity: O((N + Q) log N)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

vector<int> g[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;
long long fenwick[MAXN];
int N,Q;

void dfs(int v, int p){

    tin[v] = ++timer;

    for(int u : g[v]){
        if(u == p) continue;
        dfs(u,v);
    }

    tout[v] = timer;
}

void update(int i, long long val){
    for(; i <= N; i += i & -i)
        fenwick[i] += val;
}

long long query(int i){
    long long s = 0;
    for(; i > 0; i -= i & -i)
        s += fenwick[i];
    return s;
}

int main(){

    cin >> N >> Q;

    for(int i=0;i> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1,0);

    while(Q--){

        int type;
        cin >> type;

        if(type == 1){

            int v,x;
            cin >> v >> x;

            update(tin[v], x);
            update(tout[v]+1, -x);

        }
        else{

            int v;
            cin >> v;

            cout << query(tin[v]) << "\n";

        }
    }
}

การบันทึกเวลา Entry/Exit ใน DFS

int timer = 0;

void dfs(int s, int e) {

tin[s] = ++timer; // เวลาเข้า

for (auto u : adj[s]) {

if (u == e) continue;

dfs(u, s);

}

tout[s] = timer; // เวลาออก

}

"ถ้า ( tin[u] \le tin[v] ) และ ( tout[u] \ge tout[v] ) แปลว่า u เป็นบรรพบุรุษของ v"

ข้อมูลบนเส้นเชื่อม (Values on Edges)

Edge

เทคนิคการแปลง Edge เป็น Node:

ในต้นไม้ เรามักจะเก็บค่าของเส้นเชื่อมไว้ที่ โหนดลูก (Child Node) เนื่องจากทุกลูกจะมีพ่อ (Parent) เพียงคนเดียวเสมอ ยกเว้น Root ซึ่งจะไม่มีค่าเส้นเชื่อมอยู่เหนือมัน

ช่วยให้เราสามารถใช้เทคนิค Euler Tour หรือ Tree DP กับค่าบนเส้นเชื่อมได้
เวลาทำ Path Query ต้องระวังไม่นับค่าของ LCA เข้ามา (เพราะมันแทนเส้นเชื่อมเหนือ LCA)

ข้อควรระวังในการเขียน Traversal

Stack Overflow

ต้นไม้ที่ลึกมาก (เช่น ( 10^5 ) โหนด) อาจทำให้ Recursion ค้างได้ ลองเพิ่มขนาด Stack หรือใช้ Iterative DFS

Parent Checking

อย่าลืมส่งพารามิเตอร์พ่อ (Parent) เสมอเพื่อกันไม่ให้เดินย้อนกลับไปจุดเดิมจนติดลูปไม่รู้จบ

"Traversal is the bridge between Structure and Algorithm."

การเตรียมข้อมูล Binary Lifting (Preprocessing)

// ให้ up[v] = parent[v] จากการทำ DFS

for (int k = 1; k < LOG; k++) {

for (int v = 1; v <= n; v++) {

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

}

แนวคิด: บรรพบุรุษลำดับที่ ( 2^k ) ของ ( v ) คือบรรพบุรุษลำดับที่ ( 2^{k-1} ) ของบรรพบุรุษลำดับที่ ( 2^{k-1} ) ของ ( v ) เราใช้เวลา ( O(n \log n) ) ในการเติมตารางนี้ให้ครบ

อ้างอิงเทคนิค: https://usaco.guide/gold/LCA

ขั้นตอนการสืบค้น LCA (Query)

1. ปรับระดับ (Lift)

ถ้า ( depth[u] < depth[v] ) ให้สลับตัวแปร แล้วกระโดด ( u ) ขึ้นไปให้สูงเท่ากับ ( v ) โดยใช้เลขฐานสองของผลต่างระดับ

2. กระโดดร่วม (Binary Jump)

ถ้ายังไม่เจอกัน ให้ลองกระโดดขึ้นไป ( 2^k ) ขั้นพร้อมกันจาก ( k ) ใหญ่ไปหาเล็ก โดยมีเงื่อนไขว่าต้อง "ไม่กระโดดจนเลยจุดที่เจอกัน"

"ผลลัพธ์สุดท้ายคือ parent ของโหนดที่ u และ v กระโดดไปหยุด"

การหาบรรพบุรุษลำดับที่ k

"กระโดดขึ้นไปตาม Bit ของ k ในเวลา ( O(\log k) )"

for (int i = 0; i < LOG; i++) {
if ((k >> i) & 1) v = up[v][i];
}

เทคนิคนี้ช่วยให้เราสามารถตอบคำถาม "ใครคือหัวหน้าลำดับที่ 100 ของพนักงานคนนี้" ได้อย่างรวดเร็วมาก แม้ต้นไม้จะมีความสูงถึงระดับแสนโหนดก็ตาม

โจทย์ฝึกหัด: https://cses.fi/problemset/task/1687

Tree DP: เซตอิสระที่มีน้ำหนักสูงสุด

โจทย์: เลือกโหนดให้มีค่าน้ำหนักรวมมากที่สุด โดยห้ามเลือกโหนดที่ติดกัน

นิยามสถานะ:

• ( dp[v] ): ค่าสูงสุดใน Subtree ของ ( v ) โดย ไม่เลือก ( v )
• ( dp[v][1] ): ค่าสูงสุดใน Subtree ของ ( v ) โดย เลือก ( v )

dp[v] = Σ max(dp[u], dp[u][1])
dp[v][1] = weight[v] + Σ dp[u]

Euler Tour: การอัปเดตและหาค่า Subtree

เมื่อเราแปลง Tree เป็น Array ผ่านช่วง ( [tin[v], tout[v]] ):

Node Update

อัปเดตค่าที่ตำแหน่ง ( tin[v] ) ใน Fenwick Tree

Subtree Query

หาผลรวมช่วง ( [tin[v], tout[v]] ) ในเวลา ( O(\log n) )

"นี่คือกุญแจสำคัญในการแก้โจทย์ Dynamic Tree Connectivity เบื้องต้น"

ศึกษาเพิ่มเติม: https://cses.fi/book/book.pdf (Chapter 18)

จุดศูนย์กลางของต้นไม้ (Tree Center)

Center

"โหนดที่ทำให้ระยะทางไปยัง Leaf ที่ไกลที่สุดสั้นที่สุด"

วิธีการหา:
1. หาเส้น Diameter
2. จุดศูนย์กลางจะอยู่กึ่งกลางของเส้นทาง Diameter นั้นเสมอ
(ต้นไม้อาจมีจุดศูนย์กลางได้ 1 หรือ 2 จุด)

ใช้ในการเลือกจุดกระจายสัญญาณหรือจุดพักที่มีประสิทธิภาพที่สุดบนโครงข่าย

เทคนิคการ "ติดราก" (Rooting)

โจทย์มักให้ข้อมูลเป็นเส้นเชื่อมลอยๆ (Unrooted Tree) การเลือก Root ที่เหมาะสมจะช่วยให้ใช้ Tree DP ได้ง่ายขึ้น:

เลือกโหนด 1 เป็น Root เสมอถ้าไม่มีเหตุผลอื่น (มาตรฐานสากล)
การ Root ต้นไม้ช่วยให้เรานิยามความสัมพันธ์ "พ่อ-ลูก" ได้ชัดเจน
ระวัง: บางอัลกอริทึมให้ผลลัพธ์เปลี่ยนไปตาม Root (ต้องตรวจสอบความถูกต้อง)

เลือกใช้เครื่องมือไหนดี?

DFS (Depth-First)

• เก็บข้อมูล Subtree ได้ดีเยี่ยม (Post-order)
• ใช้กับเทคนิค Euler Tour และ DP
• ตรวจสอบความเป็นบรรพบุรุษ (tin/tout)
• เสี่ยงต่อ Stack Overflow ในต้นไม้ลึก

BFS (Breadth-First)

• หา Shortest Path บนต้นไม้ไม่มีน้ำหนัก
• เยี่ยมชมทีละระดับ (Level-order)
• เหมาะกับการหาโหนดในระยะ ( k )
• ใช้หน่วยความจำ (Queue) มากในต้นไม้ที่กว้าง

โจทย์แนะนำ: Tree Matching

URL: https://cses.fi/problemset/task/1130

หาจำนวนเส้นเชื่อมที่มากที่สุดที่ห้ามมีจุดปลายร่วมกัน (Matching)

คีย์เวิร์ด:

เป็นโจทย์ที่ฝึกใช้ Tree DP (เลือก/ไม่เลือก) และการจัดการสถานะที่ขึ้นอยู่กับการตัดสินใจของโหนดพ่อและลูกพร้อมกัน

โจทย์แนะนำ: Distance Queries

URL: https://cses.fi/problemset/task/1135

มีคำถาม ( q ) ข้อ แต่ละข้อให้หาความห่างระหว่างโหนด ( u ) และ ( v )

บททดสอบ:

ฝึกฝนการเขียน LCA ด้วย Binary Lifting และการใช้ความลึก (Depth) ในการหาคำตอบอย่างรวดเร็ว (Preprocessing ( O(n \log n) ), Query ( O(\log n) ))

บทสรุปช่วงบ่าย

ความรู้ใหม่: Binary Lifting สำหรับ Ancestor/LCA

เทคนิคพิเศษ: Euler Tour สำหรับ Subtree Range Queries

แนวคิดหลัก: Dynamic Programming on Trees

คุณสมบัติ: Unique Path และ Tree Diameter

"คุณพร้อมสำหรับการลงมือปฏิบัติแก้โจทย์ต้นไม้ในช่วงสุดท้ายของวันนี้แล้ว!"

Let's Practise!

15:00 - 17:00

ภารกิจสุดท้ายของ Day 06:

1. เข้าสู่ระบบ CSES และ AtCoder
2. เลือกโจทย์ในหัวข้อ Tree Algorithms
3. ประยุกต์ใช้ DFS/LCA/Diameter ที่เรียนมาวันนี้
4. ปรึกษาผู้ช่วยสอนหากติดขัดเรื่อง Implementation

Tree Traversal Applications การประยุกต์ใช้ BFS และ DFS ในปัญหาต้นไม้

หัวข้อการบรรยายช่วงบ่าย

ทำไมการท่องไปใน Tree ถึงง่ายกว่า Graph ทั่วไป?

การหาขนาดของต้นไม้ย่อย (Subtree Size)

ตัวอย่างโจทย์และการรับข้อมูล

ขั้นตอนการคำนวณ (Step-by-Step)

โจทย์ประยุกต์: การนับค่าใน Subtree

การหาระยะทางและความลึก

Depth (จากบนลงล่าง)

Height (จากล่างขึ้นบน)

โจทย์: การหาเส้นผ่านศูนย์กลาง (Tree Diameter)

การประยุกต์ใช้ DFS เพื่อหาระยะทางไกลสุด

พื้นฐาน Dynamic Programming บนต้นไม้

โจทย์: เซตอิสระที่ใหญ่ที่สุด (Maximum Independent Set)

C++ Implementation for Tree DP

BFS: ระยะทางสั้นที่สุดและเลเยอร์

โจทย์: ระยะห่างจากโหนดเริ่ม (Tree Distance)

C++ Implementation for Tree BFS

ปัญหาเส้นผ่านศูนย์กลาง (Tree Diameter)

ตัวอย่างโจทย์: ระยะทางไกลสุดในเครือข่าย

C++ Solution: Tree Diameter (Two-DFS)

อัลกอริทึม 2-DFS เพื่อหา Diameter

โจทย์: เครือข่ายที่ยาวที่สุด

กลยุทธ์การเขียนโปรแกรม 2-DFS

C++ Solution for Tree Diameter

การสืบค้นบรรพบุรุษ (Ancestors)

โจทย์: ใครคือบรรพบุรุษของฉัน?

กลยุทธ์: Binary Lifting

C++ Solution: K-th Ancestor

บรรพบุรุษร่วมที่ต่ำที่สุด (Naive LCA)

LCA: กลยุทธ์ Binary Lifting

C++ Solution: Binary Lifting LCA

Binary Lifting: ยกระดับความเร็วในการหา Ancestor

โจทย์: บรรพบุรุษร่วมที่ต่ำที่สุด (LCA)

อัลกอริทึม LCA (Method 1)

C++ Implementation: get_lca

การหาระยะทางระหว่างโหนดใดๆ

โจทย์: ระยะทางที่สั้นที่สุดระหว่างเพื่อนบ้าน

แนวทางการเขียนโปรแกรม

C++ Solution: Path Distance

Tree DP: การหาผลรวมในต้นไม้ย่อย

จุดประสงค์:

โจทย์: งบประมาณรวมของแผนก

แนวทางการเขียนโปรแกรม

C++ Solution: Subtree Sum DP

การหา Diameter ด้วยแนวคิด DP

โจทย์: เส้นทางที่ยาวที่สุดในเครือข่าย

กลยุทธ์การประมวลผลสถานะ

C++ Solution: Diameter via DP

เทคนิคการทำให้ต้นไม้แบน (Euler Tour)

ตัวอย่างโจทย์: Subtree Sum Query

แนวคิดการแก้ปัญหา

C++ Implementation

Euler Tour และการทํา Range Queries

ตัวอย่างโจทย์: Subtree Add Query

แนวคิดการแก้ปัญหา

C++ Implementation

การบันทึกเวลา Entry/Exit ใน DFS

ข้อมูลบนเส้นเชื่อม (Values on Edges)

ข้อควรระวังในการเขียน Traversal

Stack Overflow

Parent Checking

การเตรียมข้อมูล Binary Lifting (Preprocessing)

ขั้นตอนการสืบค้น LCA (Query)

1. ปรับระดับ (Lift)

2. กระโดดร่วม (Binary Jump)

การหาบรรพบุรุษลำดับที่ k

Tree DP: เซตอิสระที่มีน้ำหนักสูงสุด

Euler Tour: การอัปเดตและหาค่า Subtree

Node Update

Subtree Query

จุดศูนย์กลางของต้นไม้ (Tree Center)

เทคนิคการ "ติดราก" (Rooting)

เลือกใช้เครื่องมือไหนดี?

DFS (Depth-First)

BFS (Breadth-First)

โจทย์แนะนำ: Tree Matching

คีย์เวิร์ด:

โจทย์แนะนำ: Distance Queries

บททดสอบ:

Tree Traversal Applications
การประยุกต์ใช้ BFS และ DFS ในปัญหาต้นไม้