Bữa Tiệc (BUATIEC) (HSG12 Lâm Đồng 2025 – Bài 4)

Nguồn: Đề thi HSG Tin học 12 tỉnh Lâm Đồng 2025 (Bài 4) Độ khó: Trung bình Quy hoạch động QHĐ trên cây DFS

Đề bài

Câu 4: Bữa tiệc (4.0 điểm) – dữ liệu vào BUATIEC.INP, kết quả BUATIEC.OUT.

Công ty XYZ có $N$ người được tổ chức theo sơ đồ hình cây: $K$ là cha của $L$ có nghĩa là $K$ là cấp trên trực tiếp của $L$, ông Giám đốc là gốc. Nhân viên thứ $i$ có độ vui vẻ $h_i$ $(-128 \lt h_i \lt 127)$.

Ông Giám đốc muốn tổ chức một bữa tiệc có tổng độ vui vẻ là lớn nhất và nếu có một nhân viên nào đó đi dự thì sẽ không có cấp trên trực tiếp của anh ta. Đương nhiên là ông Giám đốc phải có mặt.

Yêu cầu: Em hãy giúp ông Giám đốc tìm độ vui vẻ lớn nhất có thể.

Input: Trong file BUATIEC.INP

• Dòng đầu ghi số nguyên dương $N$ $(1 \lt N \lt 2025)$.
• Dòng thứ hai ghi $N$ số $h_1, h_2, \ldots, h_N$ $(-128 \lt h_i \lt 127)$.
• $N - 1$ dòng cuối cùng ghi 2 số $L$ và $K$.

Output: Ghi kết quả vào file BUATIEC.OUT:

• Một số nguyên là tổng độ vui vẻ lớn nhất tìm được.

(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé, không là 0 điểm đó.)

BUATIEC.INP

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

BUATIEC.OUT

5

Lời mở đầu

Bài này là bài 4 trong đề thi học sinh giỏi Tin học lớp 12 tỉnh Lâm Đồng năm 2025. Đây là một bài quy hoạch động trên cây rất kinh điển (nhiều bạn sẽ thấy quen quen với bài "Anniversary Party" nổi tiếng), rất đáng để các bạn mới học QHĐ trên cây luyện tay. Mình viết lời giải + code chi tiết, hi vọng mang đến giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Chốt lại đề: ta có một cây $N$ đỉnh, mỗi đỉnh có một trọng số $h_i$ (có thể âm). Cần chọn ra một tập đỉnh sao cho không có cặp cha – con trực tiếp nào cùng được chọn, bắt buộc chọn gốc (ông Giám đốc), và tổng trọng số là lớn nhất. Lưu ý mỗi dòng cạnh ghi $L$ trước, $K$ sau, với $K$ là cha của $L$.

Với ví dụ, cây trông như hình dưới. Giám đốc $1$ phải đi, nên hai cấp dưới trực tiếp $2$ và $3$ không được đi. Còn $4, 6$ (cấp dưới của $2$) và $5, 7$ (cấp dưới của $3$) thì đi thoải mái vì cấp trên trực tiếp của họ ở nhà. Tổng $= 1 + 1 + 1 + 1 + 1 = 5$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn bitmask · N nhỏCách 2QHĐ trên cây · O(N)

Cách 1Vét cạn mọi tập nhân viên – O(2^N · N)

Cách "làm theo đề" dễ nghĩ nhất: mỗi nhân viên chỉ có 2 trạng thái đi hoặc ở nhà, nên ta duyệt hết $2^N$ tập con bằng bitmask (bit thứ $i - 1$ bật nghĩa là nhân viên $i$ đi). Với mỗi tập:

• Bỏ qua nếu gốc (ông Giám đốc) không có mặt.
• Kiểm tra từng người $i$ được chọn: nếu cấp trên trực tiếp $cha_i$ cũng được chọn thì tập này không hợp lệ.
• Tập hợp lệ thì cộng tổng $h_i$ và cập nhật đáp án lớn nhất.

Cách này chỉ để các bạn hiểu đề và dùng làm code đối chiếu (trâu) khi sinh test, vì $N$ lên tới $2024$ thì $2^N$ là con số không tưởng.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int n, h[25], cha[25];

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i < n; i ++){
        int l, k;
        cin >> l >> k;
        cha[l] = k;
    }
    int goc = 1;
    for (int i = 1; i <= n; i ++) if (cha[i] == 0) goc = i;
    int ans = INT_MIN;
    for (int mask = 0; mask < (1 << n); mask ++){
        if (!(mask >> (goc - 1) & 1)) continue;
        bool ok = true;
        int tong = 0;
        for (int i = 1; i <= n; i ++){
            if (!(mask >> (i - 1) & 1)) continue;
            tong += h[i];
            if (cha[i] != 0 && (mask >> (cha[i] - 1) & 1)) ok = false;
        }
        if (ok) ans = max(ans, tong);
    }
    cout << ans << endl;
}

n = int(input())
h = [0] + list(map(int, input().split()))
cha = [0] * (n + 1)
for _ in range(n - 1):
    l, k = map(int, input().split())
    cha[l] = k

goc = 1
for i in range(1, n + 1):
    if cha[i] == 0:
        goc = i

ans = None
for mask in range(1 << n):
    if not (mask >> (goc - 1) & 1):
        continue
    ok = True
    tong = 0
    for i in range(1, n + 1):
        if not (mask >> (i - 1) & 1):
            continue
        tong += h[i]
        if cha[i] != 0 and (mask >> (cha[i] - 1) & 1):
            ok = False
            break
    if ok and (ans is None or tong > ans):
        ans = tong
print(ans)

Không gian$O(N)$

Thời gian$O(2^N \cdot N)$

Chỉ chạy được với N rất nhỏ

Khoảng $N \le 20$ là hết cỡ. Với $N$ cỡ $2000$ như đề thì chắc chắn TLE, nên ta cần cách 2.

Cách 2Quy hoạch động trên cây – O(N)

Chúng ta sẽ sử dụng quy hoạch động trên cây để giải quyết bài toán này. Gọi:

Trạng thái QHĐ

$f[u][j]$ là độ vui vẻ tối đa có thể tạo ra nếu chỉ xét riêng bài toán trên cây con gốc $u$, với $j \in \{0, 1\}$: $j = 1$ nếu nhân viên $u$ có tham gia, còn $j = 0$ thì ngược lại (nhân viên $u$ ở nhà).

Ta có công thức truy hồi sau, với $v$ chạy qua các nhân viên nhận $u$ làm sếp trực tiếp (các con của $u$):

• Đối với $f[u][1]$: nhân viên $u$ sẽ tham gia, đồng nghĩa với việc các nhân viên nhận $u$ làm sếp trực tiếp sẽ không tham gia (vì nếu có thì nhân viên $u$ phải ở nhà). Do đó mỗi con $v$ chỉ được lấy $f[v][0]$, đồng thời cộng thêm $h_u$ của chính $u$:
  $f[u][1] = h_u + \sum\limits_{v} f[v][0]$
• Đối với $f[u][0]$: nhân viên $u$ sẽ không tham gia. Do đó các nhân viên nhận $u$ làm sếp trực tiếp có cả hai lựa chọn là tham gia hoặc không, ta lấy cái nào lớn hơn:
  $f[u][0] = \sum\limits_{v} \max(f[v][0],\ f[v][1])$

Lá (nhân viên không có cấp dưới) thì $f[u][1] = h_u$, $f[u][0] = 0$. Ta tính bằng DFS từ gốc: gọi đệ quy xuống hết các con, con nào xong thì cộng ngay vào cha. Vì ông Giám đốc bắt buộc có mặt nên đáp án là $f[\text{gốc}][1]$ (chứ không phải $\max$ của 2 trạng thái).

Vì sao độ vui vẻ âm không làm sai?

$h_u$ âm thì $f[u][1]$ sẽ nhỏ, khi đó ở cha của $u$ (nếu cha ở nhà) hàm $\max(f[u][0], f[u][1])$ tự chọn cho $u$ ở nhà. Chỉ có ông Giám đốc là "bị ép" đi dù $h$ âm, đúng như đề yêu cầu.

Ví dụ nhỏ để thấy điều này: Giám đốc có $h = -10$, hai cấp dưới vui vẻ $8$ và $7$. Nếu không bắt buộc, ta sẽ cho Giám đốc ở nhà để lấy $8 + 7 = 15$. Nhưng Giám đốc phải đi nên hai người kia phải ở nhà. Em bấm nút "Giám đốc âm" trong khung minh hoạ để xem nhé.

Minh hoạ tính f từ lá lên gốc

Em nhập độ vui vẻ $h_1, h_2, \ldots$ và các cặp $L\ K$ ($K$ là cấp trên của $L$) rồi bấm Tiếp. Dưới mỗi đỉnh là cặp giá trị $f[u][1] \,/\, f[u][0]$ khi đỉnh đó được chốt; cuối cùng mình lần ngược từ gốc để tô ra ai được đi dự tiệc.

h (cách nhau dấu cách) Các cặp L K

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int f[3005][2];
int n;
int k, l;
int h[3005];
bool coCha[3005];
vector<int> e[3005];

void dfs(int x){
    f[x][1] = h[x];
    for (auto v : e[x]){
        dfs(v);
        f[x][1] += f[v][0];
        f[x][0] += max(f[v][0], f[v][1]);
    }
    return;
}

signed main(){
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i < n; i ++){
        cin >> l >> k;
        e[k].push_back(l);
        coCha[l] = true;
    }
    int goc = 1;
    for (int i = 1; i <= n; i ++) if (!coCha[i]) goc = i;
    dfs(goc);
    cout << f[goc][1] << endl;
}

import sys
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    h = [0] + [int(x) for x in data[1:n + 1]]
    e = [[] for _ in range(n + 1)]
    coCha = [False] * (n + 1)
    p = n + 1
    for _ in range(n - 1):
        l, k = int(data[p]), int(data[p + 1])
        p += 2
        e[k].append(l)
        coCha[l] = True

    f = [[0, 0] for _ in range(n + 1)]

    def dfs(x):
        f[x][1] = h[x]
        for v in e[x]:
            dfs(v)
            f[x][1] += f[v][0]
            f[x][0] += max(f[v][0], f[v][1])

    goc = 1
    for i in range(1, n + 1):
        if not coCha[i]:
            goc = i
    dfs(goc)
    print(f[goc][1])

main()

Tìm gốc cho chắc ăn

Trong code gốc mình gọi thẳng dfs(1) vì ví dụ có Giám đốc là nhân viên $1$. Nhưng đề chỉ nói "ông Giám đốc là gốc" chứ không nói gốc là $1$, nên ở đây mình thêm mảng coCha để tìm người duy nhất không có cấp trên làm gốc – an toàn hơn mà chỉ tốn thêm một vòng for $O(N)$.

C++▶ Chạy tay từng dòng codeCách 2: DFS từ gốc, tính f[x][1] và f[x][0] từ các con.

Dữ liệu vào (stdin) – sửa thoải mái7 1 1 1 1 1 1 1 2 1 3 1 4 2 6 2 5 3 7 3

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define int long long

3using namespace std;

4

5int f[3005][2];

6int n;

7int k, l;

8int h[3005];

9bool coCha[3005];

10vector<int> e[3005];

11

12void dfs(int x){

13 f[x][1] = h[x];

14 for (auto v : e[x]){

15 dfs(v);

16 f[x][1] += f[v][0];

17 f[x][0] += max(f[v][0], f[v][1]);

18 }

19 return;

20}

21

22signed main(){

23 cin >> n;

24 for (int i = 1; i <= n; i ++) cin >> h[i];

25 for (int i = 1; i < n; i ++){

26 cin >> l >> k;

27 e[k].push_back(l);

28 coCha[l] = true;

29 }

30 int goc = 1;

31 for (int i = 1; i <= n; i ++) if (!coCha[i]) goc = i;

32 dfs(goc);

33 cout << f[goc][1] << endl;

34}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng f, h và danh sách con e đều $O(N)$.
• Thời gian: mỗi đỉnh được gọi dfs đúng một lần, mỗi cạnh được duyệt đúng một lần ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Python và đệ quy sâu

Cây có thể là một "dây xích" dài $N - 1$ tầng, nên bản Python phải tăng giới hạn đệ quy bằng sys.setrecursionlimit, không là bị RecursionError (mặc định chỉ khoảng $1000$ tầng).

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test ngẫu nhiên ($N \le 16$, gốc có thể là bất kỳ nhân viên nào, $h_i$ âm dương lẫn lộn), so cách 2 với cách 1 vét cạn – khớp hết. Với $N = 2024$ (cả cây ngẫu nhiên lẫn cây dây xích sâu nhất), cách 2 chạy khoảng 0.03 giây (C++) và 0.13 giây (Python).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇