Quy hoạch động trên cây

Mức độ: Chuyên sâu

Cây là đồ thị liên thông không có chu trình: n đỉnh, n - 1 cạnh. Chọn một đỉnh làm gốc thì mỗi đỉnh có một cha và các con, và cây con của u là u cùng mọi đỉnh nằm dưới u. Các cây con của những đứa con khác nhau không chung đỉnh nào, nên đáp án cho cây con của u thường ghép được từ đáp án cho cây con của các con. Đó là quy hoạch động trên cây: tính từ lá lên gốc.

Thứ tự tính: từ lá lên gốc

Cần tính mọi đứa con trước cha. Cách an toàn cho n lớn (không đệ quy): chạy BFS từ gốc để có thứ tự BFS và cha của mỗi đỉnh, rồi đi thứ tự đó ngược lại. Trong thứ tự BFS, cha luôn đứng trước con, nên đi ngược thì con luôn được xử lý trước cha.

Ví dụ: kích thước cây con sz[u] = 1 + tổng sz của các con.

Python

import sys
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
ke = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(du_lieu[1 + 2 * i]), int(du_lieu[2 + 2 * i])
    ke[u].append(v)
    ke[v].append(u)
cha = [0] * (n + 1)
thu_tu = [1]                          # thứ tự BFS từ gốc 1
cha[1] = -1
for u in thu_tu:
    for v in ke[u]:
        if v != cha[u]:
            cha[v] = u
            thu_tu.append(v)
sz = [1] * (n + 1)
for u in reversed(thu_tu):            # con trước cha
    if cha[u] > 0:
        sz[cha[u]] += sz[u]
print(*sz[1:])

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> ke(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    vector<int> cha(n + 1, 0), thuTu = {1};      // thứ tự BFS từ gốc 1
    cha[1] = -1;
    for (size_t k = 0; k < thuTu.size(); k++) {
        int u = thuTu[k];
        for (int v : ke[u])
            if (v != cha[u]) {
                cha[v] = u;
                thuTu.push_back(v);
            }
    }
    vector<int> sz(n + 1, 1);
    for (int k = n - 1; k >= 0; k--) {            // con trước cha
        int u = thuTu[k];
        if (cha[u] > 0) sz[cha[u]] += sz[u];
    }
    for (int u = 1; u <= n; u++) cout << sz[u] << (u < n ? ' ' : '\n');
    return 0;
}

Hai trạng thái: chọn hay không chọn

Tập độc lập lớn nhất: chọn nhiều đỉnh nhất sao cho không có hai đỉnh nào nối trực tiếp. Đáp án cho cây con của u phụ thuộc vào việc u có được chọn không, nên mỗi đỉnh có hai giá trị:

• chon[u]: số đỉnh nhiều nhất trong cây con của u, có chọn u. Khi đó không được chọn con nào: chon[u] = 1 + tổng khong[v] qua các con v.
• khong[u]: không chọn u. Mỗi con tự do chọn hay không: khong[u] = tổng max(chon[v], khong[v]).

Đáp số là max(chon[gốc], khong[gốc]).

Cây 1 - 2, 1 - 3, 3 - 4, 3 - 5 (gốc 1): lá 2, 4, 5 có chon = 1, khong = 0. Đỉnh 3: chon = 1 + 0 + 0 = 1, khong = 1 + 1 = 2. Đỉnh 1: chon = 1 + khong[2] + khong[3] = 1 + 0 + 2 = 3, khong = max(1, 0) + max(1, 2) = 3. Đáp số 3 (ví dụ chọn 2, 4, 5).

Đổi gốc

Có bài hỏi đáp án cho mọi đỉnh làm gốc, ví dụ tổng khoảng cách từ mỗi đỉnh tới mọi đỉnh khác. Tính lại cho từng gốc mất n². Đổi gốc: tính đáp án cho gốc 1, rồi suy ra đáp án cho mỗi con từ đáp án của cha.

Gọi D[u] là tổng khoảng cách từ u. Khi chuyển từ cha p sang con v: sz[v] đỉnh trong cây con của v gần thêm 1, còn n - sz[v] đỉnh còn lại xa thêm 1:

D[v] = D[p] - sz[v] + (n - sz[v])

Đi theo thứ tự BFS (cha trước con) để D[p] luôn có trước D[v]. Cả bài chỉ hai lần đi qua cây.

Luyện tập

Gồm 15 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Tính từ lá lên gốc

Bài 1. Kích thước cây con

Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau mỗi dòng có u, v là một cạnh. In ra kích thước cây con của các đỉnh 1, 2, …, n.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	5 1 3 1 1

Kiểm tra: nhập

8
4 2
1 4
4 7
2 3
2 8
1 5
5 6

Xem đáp số

8 3 1 5 2 1 1 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Chiều cao của từng cây con

Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. Chiều cao của cây con gốc u là số cạnh trên đường dài nhất từ u đi xuống một lá trong cây con của u. In ra chiều cao cây con của các đỉnh 1, 2, …, n.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 4 5	3 0 2 1 0

Kiểm tra: nhập

8
4 2
1 4
4 7
2 3
2 8
1 5
5 6

Xem đáp số

3 1 0 2 1 0 0 0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Đường kính cây

Cây có n đỉnh. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số cạnh trên đường đi dài nhất giữa hai đỉnh của cây (đường kính).

Ví dụ:

Nhập	In ra
6 1 2 1 3 3 4 3 5 5 6	4

Kiểm tra: nhập

10
1 2
2 3
3 4
2 5
5 6
6 7
1 8
8 9
9 10

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Đường kính có trọng số

Cây có n đỉnh, mỗi cạnh có độ dài. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). In ra tổng độ dài lớn nhất của một đường đi giữa hai đỉnh.

Ví dụ:

Nhập	In ra
5 1 2 3 1 3 4 3 4 2 3 5 6	13

Kiểm tra: nhập

8
1 2 5
2 3 1
2 4 7
1 5 2
5 6 9
6 7 3
5 8 8

Xem đáp số

26

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Chọn hay không chọn

Bài 5. Tập độc lập lớn nhất

Cây có n đỉnh. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số đỉnh nhiều nhất có thể chọn sao cho không có hai đỉnh được chọn nối trực tiếp với nhau.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	3

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Tiệc công ty

Công ty có n nhân viên, nhân viên 1 là giám đốc; mỗi người khác có đúng một sếp trực tiếp. Nhân viên i có độ vui v_i. Không ai muốn dự tiệc cùng sếp trực tiếp của mình. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số v_i (0 ≤ v_i ≤ 10⁹), dòng thứ ba có n - 1 số: sếp của nhân viên 2, 3, …, n. In ra tổng độ vui lớn nhất của những người dự tiệc.

Ví dụ:

Nhập	In ra
5 3 5 4 6 1 1 1 2 2	11

Kiểm tra: nhập

8
10 2 8 4 7 3 9 5
1 1 2 2 3 3 7

Xem đáp số

33

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Đặt lính canh ở các ngã ba

Mạng đường trong khu phố là một cây n ngã ba (đỉnh), n - 1 con đường (cạnh). Một lính canh đứng ở ngã ba nào thì canh được mọi con đường nối với ngã ba đó. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số lính canh ít nhất để mọi con đường đều được canh.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	2

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đặt camera

Mạng đường là một cây n đỉnh. Một camera đặt ở đỉnh u theo dõi được u và mọi đỉnh kề với u. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số camera ít nhất để mọi đỉnh đều được theo dõi.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	2

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Tô màu cây

Cây có n đỉnh. Tô mỗi đỉnh màu trắng hoặc đen sao cho không có hai đỉnh đen kề nhau. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số cách tô, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
3 1 2 2 3	5

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

161

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đổi gốc

Bài 10. Tổng khoảng cách tới mọi đỉnh

Cây có n đỉnh. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. Với mỗi đỉnh u, in ra tổng số cạnh trên đường đi từ u tới từng đỉnh khác.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	6 9 5 8 8

Kiểm tra: nhập

8
4 2
1 4
4 7
2 3
2 8
1 5
5 6

Xem đáp số

14 14 20 12 18 24 18 20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đỉnh xa nhất từ mỗi đỉnh

Cây có n đỉnh, mỗi cạnh có độ dài. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau mỗi dòng có u, v, w (1 ≤ w ≤ 10⁹). Với mỗi đỉnh u, in ra khoảng cách từ u tới đỉnh xa u nhất.

Ví dụ:

Nhập	In ra
5 1 2 3 1 3 4 3 4 2 3 5 6	10 13 7 9 13

Kiểm tra: nhập

8
1 2 5
2 3 1
2 4 7
1 5 2
5 6 9
6 7 3
5 8 8

Xem đáp số

14 19 20 26 14 23 26 22

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Trọng tâm của cây

Cây có n đỉnh. Xóa một đỉnh u (và các cạnh nối với nó), cây tách thành các phần. Gọi m(u) là số đỉnh của phần lớn nhất. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra đỉnh u có m(u) nhỏ nhất (nếu nhiều, in đỉnh có số nhỏ nhất) và giá trị m(u).

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	3 2

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

2 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Kết hợp với cái túi

Bài 13. Ghép cặp đỉnh kề nhau

Cây có n đỉnh. Chọn nhiều cạnh nhất sao cho không có hai cạnh được chọn chung đỉnh (mỗi cạnh chọn là một cặp đỉnh kề nhau, mỗi đỉnh thuộc nhiều nhất một cặp). Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), n - 1 dòng sau là các cạnh. In ra số cạnh nhiều nhất.

Ví dụ:

Nhập	In ra
5 1 2 1 3 3 4 3 5	2

Kiểm tra: nhập

10
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đếm cặp đỉnh cách nhau k cạnh

Cây có n đỉnh. Dòng đầu có n, k (1 ≤ n ≤ 5 × 10⁴, 1 ≤ k ≤ 100), n - 1 dòng sau là các cạnh. In ra số cặp đỉnh (không kể thứ tự) mà đường đi giữa chúng có đúng k cạnh.

Ví dụ:

Nhập	In ra
5 2 1 2 1 3 3 4 3 5	4

Kiểm tra: nhập

10 3
1 2
2 3
3 4
4 5
2 6
6 7
6 8
1 9
9 10

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Chọn vùng liên thông giá trị lớn nhất

Cây có n đỉnh, gốc là đỉnh 1, đỉnh i có giá trị v_i. Chọn đúng k đỉnh tạo thành một vùng liên thông chứa gốc (đỉnh được chọn thì cha của nó cũng được chọn). Dòng đầu có n, k (1 ≤ k ≤ n ≤ 300), dòng thứ hai có n số v_i (|v_i| ≤ 10⁶), n - 1 dòng sau là các cạnh. In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
5 3 1 5 2 8 3 1 2 1 3 3 4 3 5	11

Kiểm tra: nhập

8 4
3 -2 6 1 4 7 -5 2
1 2
1 3
2 4
2 5
3 6
6 7
6 8

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.