Tính kết quả từ các nhánh của cây

Lan cần chọn các trạm phát quà trong một mạng gồm 6 địa điểm. Hai địa điểm nối trực tiếp không được cùng phát quà, nhưng Lan muốn chọn được nhiều trạm nhất. Nếu thử mọi tập địa điểm, số phương án tăng rất nhanh. Cấu trúc cây giúp Lan gom kết quả từng nhánh trước khi quyết định ở điểm giao.

Chọn một gốc để nhìn cây thành các nhánh

Một đỉnh (vertex) biểu diễn một địa điểm; một cạnh (edge) nối hai địa điểm đi trực tiếp được. Cây (tree) là mạng liên thông, không có chu trình. Liên thông nghĩa là đi được giữa mọi cặp đỉnh. Không có chu trình nghĩa là không thể đi theo các cạnh khác nhau rồi trở lại điểm xuất phát.

Một cây n đỉnh có đúng n - 1 cạnh. Ngược lại, dữ liệu có n - 1 cạnh chưa đủ chứng minh là cây nếu không biết nó liên thông. Bài này giả sử đề bảo đảm đầu vào là cây. Giữa hai đỉnh bất kỳ có đúng một đường đi đơn, tức đường không lặp đỉnh.

Hình sau dùng các cạnh 1-2, 1-3, 2-4, 2-5, 3-6. Chọn đỉnh 1 làm gốc (root):

Với gốc này, cha (parent) của một đỉnh khác gốc là đỉnh đứng ngay trước nó trên đường từ gốc. Các đỉnh có cùng cha là con (child) của cha đó. Đỉnh 2 có cha là 1 và có hai con là 4, 5. Gốc không có cha; đỉnh không có con là lá (leaf).

Cây con (subtree) gốc u gồm u và mọi đỉnh mà đường từ gốc đi qua u. Cây con gốc 2 gồm 2, 4, 5. Cây con gốc 1 là cả cây. Nếu đổi gốc, quan hệ cha con và các cây con có thể đổi, dù các cạnh không đổi.

Lưu ý lá được xác định theo gốc đã chọn. Cây chỉ có một đỉnh thì gốc cũng là lá. Khi cây có nhiều hơn một đỉnh, gốc chỉ có một hàng xóm vẫn có một con; không được gọi nó là lá theo định nghĩa trên.

Để lưu cạnh vô hướng, tạo một list hàng xóm cho mỗi đỉnh. Thêm cả hai chiều vì đề không hướng cạnh từ cha xuống con:

n = 4
edges = [(1, 2), (1, 3), (3, 4)]
adj = [[] for _ in range(n + 1)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
print(adj[1])
print(adj[3])

[2, 3]
[1, 4]

Danh sách của 3 có cả 1 và 4. Sau khi chọn gốc 1, chỉ 4 là con của 3; 1 là cha. Hướng đó được xác định khi duyệt, không phải khi đọc cạnh.

Không dùng [[]] * (n + 1) để tạo các danh sách hàng xóm. Cách đó nhân tham chiếu đến cùng một danh sách, nên thêm cạnh ở một đỉnh cũng làm các danh sách khác thay đổi:

bad = [[]] * 3
bad[1].append(7)
print(bad)
good = [[] for _ in range(3)]
good[1].append(7)
print(good)

[[7], [7], [7]]
[[], [7], []]

Duyệt từ gốc để ghi cha, rồi đảo thứ tự

Muốn tính một kết quả từ các nhánh con, ta cần xử lý con trước cha. Ta có thể tìm các đỉnh từ gốc trước, lưu thứ tự, rồi đi ngược lại. Cách này tránh phải gọi đệ quy sâu trên một cây dài như đường thẳng.

Mỗi đỉnh được lưu trong order sau cha của nó. Khi xét u, hàng xóm khác parent[u] là con của u. Điều này đúng vì đầu vào là cây; với mạng có chu trình phải có cách đánh dấu đã thăm. Gốc dùng cha giả 0, vì các đỉnh thật đánh số từ 1.

Ví dụ sau ghi parent và một thứ tự hợp lệ. Thứ tự giữa hai nhánh có thể thay đổi theo thứ tự cạnh được nhập:

n = 6
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
adj = [[] for _ in range(n + 1)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
parent = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != parent[u]:
            parent[v] = u
            order.append(v)
print("cha:", parent[1:])
print("thu tu:", order)
print("nguoc:", order[::-1])

cha: [0, 1, 1, 2, 2, 3]
thu tu: [1, 2, 3, 4, 5, 6]
nguoc: [6, 5, 4, 3, 2, 1]

Vòng for u in order của Python tiếp tục xét các phần tử vừa được thêm vào cuối order. Khi thêm v, u đã nằm trong danh sách. Do đó cha đứng trước con, và thứ tự ngược bảo đảm con đứng trước cha. Ta không cần các lá đứng liền nhau.

Ở cây một đỉnh, order chỉ chứa 1 và không có cạnh để xét. Ở cây đường thẳng, danh sách có thể dài bằng n, nhưng chương trình không tạo n lời gọi hàm lồng nhau. sys.setrecursionlimit có thể đổi giới hạn đệ quy, nhưng giới hạn quá cao có thể làm tiến trình bị lỗi. Vì vậy lời giải dưới đây dùng vòng lặp.

Với n đỉnh, danh sách kề chứa đúng 2(n - 1) lượt hàng xóm. Tạo thứ tự mất O(n) thời gian và O(n) bộ nhớ. Với n = 100000, số lượt xem hàng xóm là 199998, thay vì thử 2^100000 tập đỉnh.

Gộp kết quả của từng cây con từ dưới lên

Quy hoạch động trên cây (tree dynamic programming) lưu kết quả của bài toán con gắn với mỗi đỉnh. Trạng thái phải nói rõ phạm vi và điều kiện. Sau đó, ta gộp kết quả của các con để tính trạng thái cha. Bài 28 trình bày ý tưởng lưu kết quả cho các bài toán con.

Xét chiều cao tính bằng số cạnh từ u đến lá xa nhất trong cây con của u. Ký hiệu height[u] là chiều cao đó. Một lá có chiều cao 0 vì đường từ lá đến chính nó không dùng cạnh. Với mỗi con v, đường qua nhánh ấy có chiều dài 1 + height[v].

Vì mọi đường từ u xuống lá đều bắt đầu qua đúng một con, giá trị lớn nhất trong các nhánh là đáp án. Nếu không có con, giá trị khởi đầu 0 đã đúng. Trong hình trên, height[2] = 1, height[3] = 1 và height[1] = 2.

n = 6
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
adj = [[] for _ in range(n + 1)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
parent = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != parent[u]:
            parent[v] = u
            order.append(v)
height = [0] * (n + 1)
for u in reversed(order):
    for v in adj[u]:
        if parent[v] == u:
            height[u] = max(height[u], height[v] + 1)
print(*height[1:])

2 1 1 0 0 0

Để thấy việc gộp có thể dùng phép cộng thay vì max, hãy đếm lá trong từng cây con. Lá đóng góp 1. Một đỉnh có con nhận tổng số lá của các con, vì các cây con của chúng rời nhau và phủ hết lá phía dưới.

children = [[], [2, 3], [4, 5], [6], [], [], []]
order = [1, 2, 3, 4, 5, 6]
leaves = [0] * 7
for u in reversed(order):
    leaves[u] = sum(leaves[v] for v in children[u]) if children[u] else 1
print(*leaves[1:])

3 2 1 1 1 1

Hai ví dụ có cùng thứ tự xử lý nhưng khác ý nghĩa trạng thái và phép gộp. Bạn phải chọn công thức từ câu hỏi của đề. Không thể đổi max thành sum trong bài chiều cao: một đường đi chỉ đi vào một nhánh, không đi qua mọi nhánh.

Hai nhánh cao nhất giúp tìm đường kính của cây

Đường kính (diameter) là số cạnh của đường đi dài nhất giữa hai đỉnh bất kỳ. Đường đi đó có một đỉnh gần gốc nhất. Từ đỉnh ấy, đường đi xuống tối đa hai nhánh con khác nhau. Một đầu cũng có thể chính là đỉnh ấy, khi đó chỉ cần một nhánh.

Với từng đỉnh u, tìm hai giá trị lớn nhất height[v] + 1 từ các con v. Gọi chúng là h1 và h2; giá trị thiếu được tính là 0. Đường dài nhất có đỉnh gần gốc nhất là u dài h1 + h2. Chiều cao của u là h1.

Mọi đường đi đều có đúng một đỉnh gần gốc nhất. Khi xét đỉnh đó, hai nhánh cao nhất cho đường dài ít nhất bằng đường đang xét. Hai nhánh khác nhau chỉ chung u, nên ghép chúng cũng tạo được một đường hợp lệ. Vì vậy giá trị lớn nhất trên mọi đỉnh chính là đường kính.

Với cây sáu đỉnh ở hình đầu bài, đường 4-2-1-3-6 có bốn cạnh. Đoạn sau tính đường kính từ danh sách con đã xác định:

children = [[], [2, 3], [4, 5], [6], [], [], []]
height = [0] * 7
diameter = 0
for u in [6, 5, 4, 3, 2, 1]:
    h1 = h2 = 0
    for v in children[u]:
        h = height[v] + 1
        if h > h1:
            h1, h2 = h, h1
        elif h > h2:
            h2 = h
    height[u] = h1
    diameter = max(diameter, h1 + h2)
print(diameter)

4

Kết quả là 4. Hai nhánh cùng chiều cao vẫn được tính nếu đến từ hai con khác nhau. Với một đỉnh, cả hai chiều cao đều bằng 0 nên đường kính bằng 0. Không chỉ xét gốc: đường dài nhất có thể nằm hoàn toàn trong một cây con.

Mỗi cạnh được xét số lần cố định, nên thuật toán mất O(n) thời gian và O(n) bộ nhớ. Với n = 100000, danh sách kề có 199998 lượt hàng xóm. Cách duyệt lặp không tạo chuỗi lời gọi đệ quy dài 100000.

Hai trạng thái giữ thông tin cần thiết ở cạnh nối với cha

Trở lại bài chọn trạm: không được chọn đồng thời hai đầu của một cạnh. Một tập độc lập (independent set) là tập đỉnh thỏa điều kiện đó. Ta tìm số đỉnh lớn nhất có thể chọn; tập rỗng cũng hợp lệ.

Chỉ lưu số lớn nhất của một cây con là chưa đủ. Cha cần biết con có được chọn hay không, vì quyết định ở hai đầu cạnh liên quan nhau. Định nghĩa hai trạng thái cho cây con gốc u:

Nếu chọn u, không được chọn bất kỳ con nào. Bắt đầu take[u] = 1, rồi cộng skip[v] của từng con v. Nếu bỏ u, mỗi con được chọn hoặc bỏ. Bắt đầu skip[u] = 0, rồi cộng max(take[v], skip[v]) cho từng con.

Hai cây con của hai con khác nhau không có cạnh nối trực tiếp. Nếu có, cạnh ấy cùng đường đi qua cha sẽ tạo chu trình. Vì vậy, một lựa chọn hợp lệ trong nhánh này không cản trở lựa chọn trong nhánh kia. Ta được phép cộng kết quả tối ưu của từng nhánh.

Tại lá, take = 1 và skip = 0. Đây là trường hợp cơ sở. Giả sử hai trạng thái của mọi con đều đúng. Hai công thức xét đầy đủ các lựa chọn hợp lệ ở từng nhánh, nên trạng thái của cha cũng đúng. Lập luận đi từ lá lên gốc chứng minh kết quả toàn cây.

Ví dụ ở hình: lá 4, 5, 6 có cặp (take, skip) = (1, 0). Đỉnh 2 nhận (1, 2), còn đỉnh 3 nhận (1, 1). Đỉnh 1 nhận (4, 3), nên đáp án là 4. Một cách chọn là 1, 4, 5, 6.

children = [[], [2, 3], [4, 5], [6], [], [], []]
order = [1, 2, 3, 4, 5, 6]
take = [1] * 7
skip = [0] * 7
for u in reversed(order):
    for v in children[u]:
        take[u] += skip[v]
        skip[u] += max(take[v], skip[v])
    print(u, take[u], skip[u])
print("dap an:", max(take[1], skip[1]))

6 1 0
5 1 0
4 1 0
3 1 1
2 1 2
1 4 3
dap an: 4

Thứ tự hai con không làm thay đổi tổng. Đáp án không nhất thiết bắt buộc chọn gốc. Chẳng hạn, nếu gốc có ba con đều là lá, bỏ gốc và chọn ba lá tốt hơn chọn riêng gốc:

take_root = 1 + 0 + 0 + 0
skip_root = max(1, 0) + max(1, 0) + max(1, 0)
print(take_root, skip_root, max(take_root, skip_root))

1 3 3

Nếu có một đỉnh, câu trả lời là 1. Nếu các nhánh có cùng kết quả khi chọn hoặc bỏ, max vẫn cho giá trị đúng; ta chưa cần lưu cách chọn cụ thể. Khi đề đòi in tập đỉnh, cần thêm bước khôi phục lựa chọn theo trạng thái cha.

Ghép cách đọc dữ liệu với hai trạng thái

Đề cho n, sau đó là n - 1 cạnh. Các đỉnh đánh số từ 1 đến n. Chương trình sau đọc cây, tạo thứ tự, rồi tính hai trạng thái. Mẫu có 6 đỉnh như hình đầu bài:

6
1 2
1 3
2 4
2 5
3 6

import sys
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
adj = [[] for _ in range(n + 1)]
for i in range(1, len(data), 2):
    u, v = data[i], data[i + 1]
    adj[u].append(v)
    adj[v].append(u)
parent = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != parent[u]:
            parent[v] = u
            order.append(v)
take = [1] * (n + 1)
skip = [0] * (n + 1)
for u in reversed(order):
    for v in adj[u]:
        if parent[v] == u:
            take[u] += skip[v]
            skip[u] += max(take[v], skip[v])
print(max(take[1], skip[1]))

4

Kết quả là 4 như phép tính ở trên. Đọc toàn bộ dữ liệu giúp tránh gọi input() cho từng cạnh. Hai vòng xem danh sách kề đều xét 2(n - 1) lượt. Phần còn lại xử lý mỗi đỉnh số lần không đổi, nên thời gian và bộ nhớ đều O(n).

Chọn một gốc khác chỉ thay cách chia cây thành cây con. Mỗi tập hợp lệ của toàn cây vẫn được xét đúng một lần thông qua trạng thái ở gốc mới. Vì vậy giá trị tối ưu không đổi theo gốc, dù các trạng thái trung gian thay đổi.

Trọng số âm làm việc chọn và bỏ khác nhau

Giả sử trạm u mang giá trị weight[u], có thể âm. Mục tiêu là tổng giá trị lớn nhất và được phép không chọn trạm nào. Ý nghĩa hai trạng thái vẫn như cũ, nhưng take[u] bắt đầu bằng weight[u] thay vì 1. skip[u] vẫn bắt đầu bằng 0.

Xét ba trạm trên một đường: trọng số lần lượt là 4, 9, 4. Chọn hai đầu được 8, còn chọn đỉnh giữa được 9. Không thể kết luận chọn nhiều đỉnh nhất sẽ cho tổng trọng số lớn nhất:

children = [[], [2], [3], []]
weight = [0, 4, 9, 4]
take = weight[:]
skip = [0] * 4
for u in [3, 2, 1]:
    for v in children[u]:
        take[u] += skip[v]
        skip[u] += max(take[v], skip[v])
print(max(take[1], skip[1]))

9

Với một đỉnh trọng số -5, take là -5 còn skip là 0. Nếu đề cho phép tập rỗng, đáp án là 0. Nếu đề bắt buộc chọn ít nhất một đỉnh, hai trạng thái này chưa phân biệt tập rỗng với tập không rỗng. Khi đó cần bổ sung trạng thái hoặc xử lý riêng có chứng minh.

weight = -5
take = weight
skip = 0
print(max(take, skip))

0

Mỗi nhánh vẫn được gộp độc lập khi biết trạng thái của cha. Công thức chỉ thay đóng góp tại đỉnh, nên bằng chứng đúng và độ phức tạp vẫn giữ nguyên. Với 100000 đỉnh, số lượt xử lý tỷ lệ với 100000, không tỷ lệ với tổng trọng số.

Đếm các tập hợp lệ bằng phép nhân giữa các nhánh

Một đề khác hỏi có bao nhiêu tập đỉnh không kề nhau, thay vì hỏi tập lớn nhất. Hai trạng thái vẫn phân biệt chọn và bỏ gốc cây con. Lần này, take[u] và skip[u] là số cách tương ứng, không phải số đỉnh hay tổng trọng số.

Ở lá, mỗi trạng thái có đúng một cách: chọn lá hoặc bỏ lá. Vì thế cả hai giá trị khởi đầu bằng 1. Khi chọn u, mỗi con v phải bị bỏ và có skip[v] cách. Chọn một cách ở nhánh thứ nhất và một cách ở nhánh thứ hai tạo ra một cách ghép duy nhất. Do đó nhân số cách của tất cả các nhánh.

Khi bỏ u, một nhánh có take[v] + skip[v] cách. Hai nhóm này không trùng nhau vì một nhóm chọn v và nhóm kia bỏ v. Nhân các tổng đó cho mọi con. Với đỉnh không có con, tích rỗng bằng 1, khớp trường hợp lá.

Xét cây sao có gốc 1 và hai lá 2, 3. Khi chọn gốc, có một cách là {1}. Khi bỏ gốc, mỗi lá có hai lựa chọn độc lập, tạo bốn cách. Bốn cách này bao gồm cả tập rỗng. Đoạn mã sau tính hai trạng thái:

children = [[], [2, 3], [], []]
take = [1] * 4
skip = [1] * 4
for u in [3, 2, 1]:
    for v in children[u]:
        take[u] *= skip[v]
        skip[u] *= take[v] + skip[v]
print(take[1], skip[1], take[1] + skip[1])

1 4 5

Tổng số cách có thể rất lớn. Nếu đề yêu cầu lấy dư theo 1000000007, lấy dư sau mỗi phép nhân và phép cộng. Việc này giữ cùng phần dư với kết quả chính xác. Mỗi cạnh vẫn được xét số lần cố định; số phép tính là O(n), và các giá trị dư được giữ trong giới hạn của mô-đun.

Nếu đề loại tập rỗng, trừ một khỏi tổng cuối rồi lấy dư. Không được trừ một ở từng nhánh: một nhánh rỗng vẫn ghép hợp lệ với nhánh khác có đỉnh được chọn. Trạng thái đếm và trạng thái tối ưu dùng cùng ý tưởng tách nhánh nhưng không thể thay phép nhân bằng phép cộng tùy ý.

Lỗi thường gặp

Tóm tắt

• Cây liên thông và không chu trình; chọn gốc để xác định cha, con và cây con.
• Lưu cạnh hai chiều, ghi thứ tự cha trước con rồi đảo lại để tính từ dưới lên.
• Mỗi trạng thái phải ghi rõ phạm vi cây con và điều kiện tại gốc của nó.
• Khi chọn một đỉnh, các con phải bỏ; khi bỏ đỉnh ấy, mỗi con chọn trạng thái tốt hơn.
• Lời giải dùng O(n) thời gian và O(n) bộ nhớ cho cây n đỉnh.

Kiểm tra nhanh

Đọc thêm

• Python: giới hạn đệ quy giải thích giới hạn và rủi ro khi tăng quá cao.
• USACO Guide: quy hoạch động trên cây giới thiệu các bài toán cùng chủ đề.