Chương 42 - Tree Dynamic Programming

Tree DP = DFS bottom-up trên cây. Mỗi node tính giá trị từ con. Pattern đặc biệt: re-rooting - tính kết quả cho từng node làm root (giảm O(n²) xuống O(n)).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Bottom-up: trả tuple (state1, state2, ...) từ con lên.
• Re-rooting: 2 lần DFS - DFS1 tính subtree, DFS2 propagate up.
• Pattern 3 state: rob/cover/skip (Camera, House Robber III).
• Diameter: top1 + top2 chiều dài từ node - không phải top1 * 2.

Khi nào dùng pattern này?

• Bài trên tree/forest có “tính cho từng node” hoặc “tổng thể tối ưu”.
• DP với 2-3 state per node (rob/skip, install/skip).
• Bài re-rooting: distance sum, max diameter from each node.

Template code

# 1) Tree DP bottom-up
def dfs(node, parent):
    state = base
    for child in graph[node]:
        if child == parent: continue
        sub = dfs(child, node)
        state = combine(state, sub)
    return state

# 2) Re-rooting (xem 42.5 cho implementation đầy đủ)
def re_root(graph, n):
    # 1st DFS: compute "down" values (subtree rooted at i).
    # 2nd DFS: propagate "up" values from parent to children.
    pass

Bài tự luyện cuối chương

• LC 543 - Diameter of Binary Tree
• LC 124 - Binary Tree Maximum Path Sum (Chương 22)

---

42.1 House Robber III (LC 337) - recap

Đã giải đầy đủ ở Chương 11.5. Tree DP với 2 state mỗi node: rob_this, skip_this.

Liên hệ với chương này

Đây là gateway cho Tree DP - pattern “trả tuple 2 giá trị từ con”. Toàn chương 42 mở rộng pattern này: Binary Tree Cameras (3 state), Diameter (track best across subtrees), Sum of Distances (re-rooting).

Code Python 3 (recap)

from typing import Optional, Tuple

class Solution:
    def rob(self, root) -> int:
        def dfs(node) -> Tuple[int, int]:
            """Trả (rob_this, skip_this)."""
            if not node:
                return 0, 0
            l_rob, l_skip = dfs(node.left)
            r_rob, r_skip = dfs(node.right)
            rob_this = node.val + l_skip + r_skip
            skip_this = max(l_rob, l_skip) + max(r_rob, r_skip)
            return rob_this, skip_this
        return max(dfs(root))

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(h) stack.

Bài tự luyện liên quan

• LC 198, 213 - House Robber I, II.
• LC 968 - Binary Tree Cameras (bài 42.2).

---

42.2 Binary Tree Cameras (LC 968)

Đề bài

Đặt camera trên cây sao cho mọi node “phủ” (camera tại node hoặc kề camera). Min số camera.

Ví dụ

Input:  root = [0, 0, null, 0, 0]
        (LC level-order serialize; 'null' = node không tồn tại;
         giá trị node ở đây không liên quan, chỉ cấu trúc cây.)
Output: 1   (số camera tối thiểu phủ tất cả node)

Ràng buộc

• 1 <= số node <= 1000
• 0 <= node.val <= 1

Clarifying questions

• Tree 1 node? → Trả 1 camera.
• Tree rỗng? → Trả 0.

Hướng tiếp cận

3 state mỗi node: - 0: chưa được phủ. - 1: được phủ (không có camera tại đây nhưng con có camera). - 2: có camera tại đây.

Greedy bottom-up: nếu child là 0 → đặt camera ở node hiện tại.

Code Python 3

class Solution:
    def minCameraCover(self, root) -> int:
        self.cnt = 0

        def dfs(node) -> int:
            if not node: return 1   # null coi như "covered"
            l = dfs(node.left)
            r = dfs(node.right)
            if l == 0 or r == 0:
                self.cnt += 1
                return 2
            if l == 2 or r == 2:
                return 1
            return 0

        if dfs(root) == 0:
            self.cnt += 1
        return self.cnt

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(h) stack.

Bình luận

• Greedy on tree: đặt camera ở node có con “uncovered” - tối ưu nhất.

Bài tự luyện liên quan

• LC 337 - House Robber III (bài 42.1)
• LC 979 - Distribute Coins in Binary Tree

---

42.3 Diameter of Binary Tree (LC 543)

Đề bài

Đường đi dài nhất giữa 2 node bất kỳ trong cây (cạnh đếm).

Ví dụ

Input:  root = [1, 2, 3, 4, 5]   (LC level-order, đọc trái → phải, tầng trên → tầng dưới)
Output: 3   (đường đi 4 → 2 → 1 → 3 hoặc 5 → 2 → 1 → 3 có 3 cạnh)

Ràng buộc

• 1 <= số node <= 10^4
• -100 <= node.val <= 100

Clarifying questions

• Tree 1 node? → Diameter = 0.
• Edge or node count? → Cạnh (theo LC).

Hướng tiếp cận

DFS bottom-up. Mỗi node trả về depth từ nó xuống. diameter qua node = left_depth + right_depth.

Code Python 3

class Solution:
    def diameterOfBinaryTree(self, root) -> int:
        self.best = 0

        def depth(node) -> int:
            if not node: return 0
            l = depth(node.left)
            r = depth(node.right)
            self.best = max(self.best, l + r)
            return 1 + max(l, r)

        depth(root)
        return self.best

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(h) stack.

Bình luận

• Bẫy: diameter = top1 + top2 (2 chiều dài nhất từ node), không phải top1 * 2.
• Follow-up: LC 124 (Max Path Sum) - Chương 22.4.

Bài tự luyện liên quan

• LC 124 - Binary Tree Maximum Path Sum (Chương 22.4)
• LC 687 - Longest Univalue Path

---

42.4 Longest Path With Different Adjacent Characters (LC 2246)

Đề bài

Input: parent: List[int] (parent array, parent[0] = -1 là root) và s: str - node i có ký tự s[i]. Tree gồm n node đánh số 0..n-1. Tìm longest path (đếm node) mà các node kề trên path có char khác nhau.

Ví dụ

Input:  parent=[-1,0,0,1,1,2], s="abacbe"
Output: 3

Ràng buộc

• n == len(parent)
• 1 <= n <= 10^5

Clarifying questions

• Tất cả node cùng char? → Trả 1 (path = 1 node).

Hướng tiếp cận

Tree DP. Mỗi node u: longest chain xuống = max(1, 1 + max chain of children with different char). Update best với top 2 chains.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def longestPath(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children = defaultdict(list)
        for i in range(1, n):
            children[parent[i]].append(i)
        self.best = 1

        def dfs(u: int) -> int:
            chains = [0]
            for v in children[u]:
                sub = dfs(v)
                if s[v] != s[u]:
                    chains.append(sub)
            chains.sort(reverse=True)
            top1 = chains[0] if chains else 0
            top2 = chains[1] if len(chains) > 1 else 0
            self.best = max(self.best, top1 + top2 + 1)
            return top1 + 1

        dfs(0)
        return self.best

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(h) stack.

Bình luận

• Bẫy: so sánh char giữa node và parent (qua s[v] != s[u]) trước khi tính.
• Follow-up: LC 543 (Diameter) cùng pattern.

Bài tự luyện liên quan

• LC 543 - Diameter of Binary Tree (bài 42.3)
• LC 1245 - Tree Diameter

---

42.5 Sum of Distances in Tree (LC 834) - Re-rooting

Đề bài

Input: n (số node) và edges: List[List[int]] - danh sách n-1 cạnh [u, v] của tree vô hướng. Trả về result: List[int] trong đó result[i] = tổng distance từ node i đến mọi node khác.

Ví dụ

Input:  n=6, edges=[[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]

Ràng buộc

• 1 <= n <= 3·10^4
• edges.length == n - 1

Clarifying questions

• n = 1? → Trả [0].
• Tree disconnected? → Theo đề: connected tree.

Hướng tiếp cận

Re-rooting kinh điển.

1. DFS thứ 1: tính count[u] = số node trong subtree u, result[0] = tổng distance từ root 0.
2. DFS thứ 2: cập nhật result[v] từ result[u] (parent của v): result[v] = result[u] - count[v] + (n - count[v]).

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        count = [1] * n
        answer = [0] * n

        def dfs1(u: int, parent: int) -> None:
            for v in graph[u]:
                if v != parent:
                    dfs1(v, u)
                    count[u] += count[v]
                    answer[u] += answer[v] + count[v]

        def dfs2(u: int, parent: int) -> None:
            for v in graph[u]:
                if v != parent:
                    answer[v] = answer[u] - count[v] + (n - count[v])
                    dfs2(v, u)

        dfs1(0, -1)
        dfs2(0, -1)
        return answer

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n).

Bình luận

• Insight re-rooting: khi root chuyển từ u sang v (v là con của u), count[v] nodes “lùi gần” 1 bước, n - count[v] nodes “lùi xa” 1 bước.

Bài tự luyện liên quan

• LC 310 - Minimum Height Trees (Chương 13.3)
• LC 2858 - Min Edge Reversals (bài 42.6)

---

42.6 Minimum Edge Reversals So Every Node Is Reachable (LC 2858)

Đề bài

Input: n và edges: List[List[int]] - mỗi cạnh [u, v] là có hướng u → v. Graph khi bỏ hướng là 1 tree (n-1 cạnh, vô hướng liên thông). Với mỗi node, đếm số cạnh phải đảo chiều để node đó reach mọi node khác.

Ví dụ

Input:  n=4, edges=[[2,0],[2,1],[1,3]]
Output: [1,1,0,2]

Ràng buộc

• 2 <= n <= 10^5
• edges.length == n - 1

Clarifying questions

• n = 1? → Trả [0].

Hướng tiếp cận

Re-rooting với “cost flip”.

1. DFS thứ 1 từ node 0: cho mỗi cạnh, nếu hướng ngược với DFS → cost +=
   1. result[0] = tổng cost.
2. DFS thứ 2: với mỗi cạnh u → v trong tree (undirected), kiểm tra direction gốc: nếu original là u → v → result[v] = result[u] + 1; nếu v → u → result[v] = result[u] - 1.

Code Python 3

from collections import defaultdict
from typing import List

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        # graph[u] = list of (v, cost) where cost = 0 if directed u→v, 1 nếu phải đảo.
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append((v, 0))    # u → v: đi xuôi
            graph[v].append((u, 1))    # v → u: nếu đi từ v ra u thì phải đảo

        result = [0] * n
        def dfs1(u: int, parent: int) -> int:
            cost = 0
            for v, c in graph[u]:
                if v != parent:
                    cost += c + dfs1(v, u)
            return cost
        result[0] = dfs1(0, -1)

        def dfs2(u: int, parent: int) -> None:
            for v, c in graph[u]:
                if v != parent:
                    # Khi root từ u → v: cạnh u-v có cost c bị flip.
                    # Cost ban đầu là c → sau khi root v: 1 - c.
                    result[v] = result[u] + (1 - 2 * c)
                    dfs2(v, u)
        dfs2(0, -1)
        return result

Phân tích độ phức tạp

• Thời gian: O(n).
• Bộ nhớ: O(n).

Bình luận

• Re-rooting là pattern xuất hiện nhiều ở contest và Hard interview.

Bài tự luyện liên quan

• LC 834 - Sum of Distances in Tree (bài 42.5)
• LC 2581 - Count Number of Possible Root Nodes

Tóm tắt chương & Quyết định

Rerooting generic template

Pass 1 (post-order): tính down[v] = đáp số subtree của v khi root tại v. Pass 2 (pre-order từ root): chuyển root từ parent p sang child c:

ans[c] = ans[p] - contribution_of_c_to_p_subtree + contribution_of_rest_to_c_subtree

Cụ thể với “sum of distances”:

ans[c] = ans[p] - size[c] + (n - size[c])

• Khi root chuyển từ p xuống c:
  • Mọi node trong subtree c lại gần root hơn 1 đơn vị ⇒ tổng distance giảm size[c].
  • Mọi node còn lại xa root hơn 1 đơn vị ⇒ tổng distance tăng n − size[c].
• Cộng lại: ans[c] = ans[p] − size[c] + (n − size[c]).

Binary Tree Cameras (LC 968) - state 0/1/2

• 0: node chưa được cover, cần camera lân cận.
• 1: node có camera.
• 2: node đã được cover (bởi child có camera) nhưng không có camera.
• Post-order rule:
  • Nếu có child = 0 ⇒ node = 1 (đặt camera, cover children).
  • Else nếu có child = 1 ⇒ node = 2 (đã được cover).
  • Else (mọi child = 2) ⇒ node = 0 (chờ parent cover).

Sum of Distances (LC 834) - trace

Tree:

   0
  /|\
 1 2 3
 |
 4

• Pass 1 (post-order, root=0):
  • down[4] = 0, size[4] = 1.
  • down[1] = down[4] + size[4] = 1, size[1] = 2.
  • down[2] = 0, size[2] = 1.
  • down[3] = 0, size[3] = 1.
  • down[0] = (1+2) + (0+1) + (0+1) = 5, size[0] = 5.
  • ⇒ ans[0] = 5.
• Pass 2: ans[1] = ans[0] - size[1] + (5 - size[1]) = 5 - 2 + 3 = 6. Tương tự cho 2, 3, 4.

Minimum Edge Reversals (LC 2858)

• Build undirected graph nhưng nhớ “hướng gốc” → cost: 0 nếu đi theo hướng gốc, 1 nếu ngược.
• Rerooting tính ans[v] = số reversal cần khi gốc cây tại v.

---