Bài 33: Cây và quy hoạch động trên cây trong C++ và Python: DFS trên cây, kích thước cây con, đường kính, tập độc lập lớn nhất, kỹ thuật đổi gốc

Series: Thuật toán chuyên sâu Độ khó: Khá Bài 33 / Thuật toán chuyên sâu Cây DFS QHĐ trên cây

// Thuật toán chuyên sâu · Bài 33

Cây và quy hoạch động trên cây: DFS, đường kính, đổi gốc

Cây là đồ thị “hiền” nhất: không có chu trình, giữa hai đỉnh chỉ có một đường đi. Nhờ vậy mọi bài toán trên cây đều có thể giải từ lá đi lên gốc, mỗi đỉnh chỉ cần xử lý một lần.

Lời mở đầu

Chào mừng em tới series thứ tư: Thuật toán chuyên sâu. Series này dành cho các bạn ôn thi HSG tỉnh vòng 2, HSG quốc gia và chuyên Tin, đã đi hết series Thuật toán nâng cao. Vẫn cách học quen thuộc: lý thuyết có hình minh hoạ, code C++ kèm Python, khung chạy tay từng dòng, các khung mô phỏng bấm từng bước và 8 bài tập có gợi ý.

Bài mở đầu nói về cây, cấu trúc xuất hiện trong gần như mọi đề thi HSG: sơ đồ công ty, mạng đường ống, cây thư mục, cây gia phả… Em đã biết duyệt đồ thị bằng BFS, DFS ở bài 21 và biết tư duy trạng thái, công thức truy hồi ở bài 19 (quy hoạch động). Hôm nay ta ghép hai thứ đó lại: chạy DFS trên cây và tính quy hoạch động từ lá lên gốc. Đây cũng là nền móng trực tiếp cho bài 34 (LCA, nhảy nhị phân) ngay sau.

Bài 33Cây, QHĐ trên cây Bài 34LCA, nhảy nhị phân Bài 35Sắp xếp topo, DAG Bài 36TPLT mạnh, khớp, cầu Bài 37Sparse Table, Lazy Bài 38Chia căn, thuật toán Mo Bài 39Z, Manacher, Trie Bài 40Số học nâng cao Bài 41Kỹ thuật tìm kiếm Bài 42Trò chơi và tổng ôn Bài 43Ghép cặp, luồng Bài 44Small-to-large, Euler tour Bài 45Tối ưu QHĐ Bài 46Hash nâng cao, Suffix Array Bài 47Heavy-Light Decomposition

Trong bài này bạn sẽ học: các khái niệm của cây có gốc (cha, con, lá, độ sâu) và cách lưu cây bằng danh sách kề; viết DFS trên cây chỉ bằng cách truyền cha, không cần mảng visited; tính kích thước cây con, thứ tự duyệt tin/tout để kiểm tra tổ tiên trong $O(1)$; tìm đường kính cây bằng hai lần BFS và vì sao nó đúng; quy hoạch động trên cây với tập độc lập trọng số lớn nhất $dp[u][0/1]$; kỹ thuật đổi gốc (rerooting) tính tổng khoảng cách từ mọi đỉnh trong $O(n)$; và cách khử đệ quy khi cây sâu tới $2 \cdot 10^5$ tầng. Có khung chạy tay DFS, 3 mô phỏng từng bước và 8 bài tập kèm gợi ý.

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

Phần 1Cây có gốc, DFS Phần 2Kích thước cây con Phần 3Đường kính cây Phần 4QHĐ trên cây Phần 5Đổi gốc, khử đệ quy Bài tập8 bài + gợi ý

Phần 1Cây có gốc và DFS truyền cha

Cây là đồ thị vô hướng liên thông và không có chu trình. Ba tính chất sau tương đương nhau, em nhớ cả ba vì đề bài hay cho theo một trong ba cách:

cây $n$ đỉnh có đúng $n - 1$ cạnh;
giữa hai đỉnh bất kỳ có đúng một đường đi đơn;
xoá một cạnh bất kỳ thì cây bị tách làm hai phần.

Khi chọn một đỉnh làm gốc (thường là đỉnh 1), cây được “treo” lên và mọi đỉnh có quan hệ trên dưới:

cha của $u$ ($par[u]$) là đỉnh kề với $u$ trên đường đi từ $u$ về gốc; gốc không có cha;
con của $u$ là các đỉnh kề còn lại; đỉnh không có con gọi là lá;
độ sâu $dep[u]$ là số cạnh từ gốc tới $u$ (gốc có độ sâu 0); chiều cao của cây là độ sâu lớn nhất;
cây con gốc $u$ gồm $u$ và mọi đỉnh nằm “phía dưới” $u$; các đỉnh trên đường từ $u$ về gốc là tổ tiên của $u$.

Hình 1. Cây ví dụ của cả bài: 8 đỉnh, cạnh 1-2, 1-3, 2-4, 2-5, 3-6, 5-7, 5-8, gốc 1 (vàng). Lá là 4, 6, 7, 8 (xanh lá). Đỉnh 5 (xanh dương) có cha là 2 và hai con 7, 8; cây con gốc 5 là {5, 7, 8}. Số dưới mỗi đỉnh là độ sâu.

Lưu cây. Đề thường cho $n - 1$ cạnh $u\ v$ mà không nói ai là cha. Ta lưu bằng danh sách kề như mọi đồ thị vô hướng ở bài 21: adj[u].push_back(v); adj[v].push_back(u);. Một số đề cho sẵn mảng cha $p_2, p_3, \ldots, p_n$, khi đó chỉ cần thêm cạnh $p_i - i$ (bài tập 2 sẽ khai thác dạng này).

DFS trên cây không cần mảng visited. Trên đồ thị thường, DFS phải đánh dấu đỉnh đã thăm để khỏi đi vòng mãi. Trên cây không có chu trình, nên từ $u$ chỉ có một cách quay lại đỉnh đã thăm: đi ngược lên cha. Vì vậy ta chỉ cần truyền thêm tham số p (cha của $u$) và bỏ qua đúng đỉnh đó:

Khuôn mẫu DFS trên cây

void dfs(int u, int p){          // p = cha của u (gốc: p = 0)
    // ... xử lý khi VÀO u (thông tin từ trên xuống: độ sâu, tổng đường đi...)
    for(int v : adj[u]){
        if(v == p) continue;     // chặn đúng một đường quay lại
        dfs(v, u);
        // ... gom kết quả của con v vào u (thông tin từ dưới lên)
    }
    // ... xử lý khi RỜI u: mọi con đã xong
}

Gần như mọi bài trên cây đều là khuôn này, chỉ khác phần “xử lý”. Thông tin đi xuống (độ sâu, khoảng cách từ gốc) tính trước khi gọi con; thông tin đi lên (kích thước, dp) tính sau khi con trả về.

Ví dụ đầu tiên: in cha và độ sâu của mọi đỉnh. Với cây ở Hình 1, chương trình in 0 1 1 2 2 3 5 5 (cha) và 0 1 1 2 2 2 3 3 (độ sâu).

Xem code C++ / Python: dfs truyền cha: tìm cha và độ sâu của mọi đỉnh (bấm để mở)

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

vector<int> adj[200005];
int par[200005], dep[200005];

void dfs(int u, int p){
    par[u] = p;
    for(int v : adj[u]){
        if(v == p) continue;             // không quay ngược lên cha
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);             // cạnh vô hướng: thêm cả hai chiều
    }
    dep[1] = 0;
    dfs(1, 0);                           // gốc 1, cha "ảo" là 0
    for(int i = 1; i <= n; i++) cout << par[i] << " \n"[i == n];
    for(int i = 1; i <= n; i++) cout << dep[i] << " \n"[i == n];
    return 0;
}

import sys
sys.setrecursionlimit(10000)       # n lớn: xem cách khử đệ quy ở phần 5

def dfs(u, p):
    par[u] = p
    for v in adj[u]:
        if v == p:
            continue               # không quay ngược lên cha
        dep[v] = dep[u] + 1
        dfs(v, u)

data = sys.stdin.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v)
    adj[v].append(u)               # cạnh vô hướng: thêm cả hai chiều
par = [0] * (n + 1)
dep = [0] * (n + 1)
dfs(1, 0)                          # gốc 1, cha "ảo" là 0
print(*par[1:])
print(*dep[1:])

Cây có trọng số và đề cho n − 1 cạnh “lung tung”

Cạnh có trọng số thì lưu vector<pair<int,int>> adj[N] và truyền thêm khoảng cách: dist[v] = dist[u] + w. Đừng tin thứ tự cạnh trong input: cạnh 4 3 không có nghĩa 4 là cha của 3. Cha–con chỉ được xác định sau khi chọn gốc và chạy DFS/BFS.

Phần 2Kích thước cây con và thứ tự duyệt

Gọi $sz[u]$ là số đỉnh trong cây con gốc $u$. Cây con gốc $u$ gồm chính $u$ cộng với các cây con của những đứa con, nên:

$sz[u] = 1 + \sum_{v \text{ là con của } u} sz[v]$

Đây là công thức quy hoạch động trên cây đơn giản nhất: muốn tính $sz[u]$ thì phải tính xong $sz$ của tất cả các con trước. DFS làm đúng thứ tự đó một cách tự nhiên: dòng sz[u] += sz[v] đặt ngay sau lời gọi dfs(v, u), lúc cây con của $v$ đã được duyệt hết.

Đỉnh $u$	1	2	3	4	5	6	7	8
cha	–	1	1	2	2	3	5	5
độ sâu	0	1	1	2	2	2	3	3
$sz[u]$	8	5	2	1	3	1	1	1
tin (vào)	1	2	7	3	4	8	5	6
tout (rời)	8	6	8	3	6	8	5	6

Bảng 1. Thông tin của cây Hình 1 sau một lần DFS từ gốc 1 (con được duyệt theo thứ tự trong danh sách kề). Ví dụ $sz[2] = 1 + sz[4] + sz[5] = 1 + 1 + 3 = 5$.

Em bấm Tự chạy trong khung chạy tay dưới đây để thấy $sz$ được cộng dồn khi DFS quay lui, và cạnh tới cha bị bỏ qua thế nào:

C++▶ Chạy tay từng dòng codedfs(u, p) tính độ sâu khi đi xuống và sz[u] khi quay lui (ô vàng: u, ô đỏ: đỉnh kề v đang xét, ô xanh lá: đã xong).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

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

2using namespace std;

4vector<int> adj[100005];

5int dep[100005], sz[100005];

7void dfs(int u, int p){

8 sz[u] = 1;

9 for(int v : adj[u]){

10 if(v == p) continue;

11 dep[v] = dep[u] + 1;

12 dfs(v, u);

13 sz[u] += sz[v];

14 }

15}

17int main(){

18 int n;

19 cin >> n;

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

21 int u, v;

22 cin >> u >> v;

23 adj[u].push_back(v); adj[v].push_back(u);

24 }

25 dfs(1, 0);

26 for(int i = 1; i <= n; i++) cout << sz[i] << " ";

27 return 0;

28}

Khung chạy tay cho thấy từng dòng code; còn để nhìn toàn cảnh trên hình cây, em dùng mô phỏng sau. Hãy thử đổi gốc thành 5: cây được “treo” lại, cha – con đổi hết và $sz$ cũng khác, nhưng $sz$ của gốc luôn bằng $n$:

MÔ PHỎNGDFS truyền cha tính kích thước cây con sz[u]Nhập các cạnh (tối đa 12 đỉnh) và gốc. Xem ngăn xếp lời gọi, cạnh tới cha bị bỏ qua và sz cộng dồn khi quay lui.

Các cạnhGốc

chưa thămđang xử lýđang chờ trên ngăn xếpđã tính xong sz

Thứ tự duyệt tin/tout. Đánh số các đỉnh theo thứ tự DFS vào chúng: $tin[u]$. Khi rời $u$, ghi lại số lớn nhất đã dùng: $tout[u]$. Vì DFS duyệt trọn cây con của $u$ rồi mới rời $u$, các đỉnh của cây con gốc $u$ nhận đúng các số liên tiếp $tin[u], tin[u] + 1, \ldots, tout[u]$, và $tout[u] = tin[u] + sz[u] - 1$. Ở Bảng 1, cây con gốc 2 là {2, 4, 5, 7, 8} có tin = 2, 3, 4, 5, 6, đúng đoạn $[2, 6]$. Hệ quả cực kỳ hữu ích:

$u$ là tổ tiên của $v$ $\iff$ $tin[u] \le tin[v] \le tout[u]$

Chỉ một phép so sánh, $O(1)$ mỗi truy vấn. Hơn nữa, “cây con gốc $u$” biến thành “đoạn $[tin[u], tout[u]]$” trên một mảng, nên các bài cập nhật / hỏi tổng trên cây con quy về bài toán trên đoạn, giải bằng Fenwick, Segment Tree ở bài 31. Kỹ thuật này gọi là trải cây (Euler tour), ta sẽ dùng nhiều ở bài 34 và bài 37.

Xem code C++ / Python: kích thước cây con, tin/tout và kiểm tra tổ tiên (bấm để mở)

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

vector<int> adj[200005];
int sz[200005], tin[200005], tout[200005], cnt = 0;

void dfs(int u, int p){
    tin[u] = ++cnt;                     // thời điểm VÀO u
    sz[u] = 1;
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];                 // cây con của v nằm gọn trong cây con của u
    }
    tout[u] = cnt;                      // thời điểm RỜI u, = tin[u] + sz[u] - 1
}

bool isAnc(int u, int v){               // u có phải tổ tiên của v (tính cả u = v)?
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i++) cout << sz[i] << " \n"[i == n];
    cin >> q;
    while(q--){
        int u, v;
        cin >> u >> v;
        cout << (isAnc(u, v) ? "YES" : "NO") << "\n";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

def dfs(u, p):
    global cnt
    cnt += 1
    tin[u] = cnt                    # thời điểm VÀO u
    sz[u] = 1
    for v in adj[u]:
        if v == p:
            continue
        dfs(v, u)
        sz[u] += sz[v]
    tout[u] = cnt                   # thời điểm RỜI u, = tin[u] + sz[u] - 1

data = sys.stdin.read().split()
pos = 0
n = int(data[pos]); pos += 1
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = int(data[pos]), int(data[pos + 1]); pos += 2
    adj[u].append(v); adj[v].append(u)
sz = [0] * (n + 1); tin = [0] * (n + 1); tout = [0] * (n + 1); cnt = 0
dfs(1, 0)
out = [' '.join(map(str, sz[1:]))]
q = int(data[pos]); pos += 1
for _ in range(q):
    u, v = int(data[pos]), int(data[pos + 1]); pos += 2
    out.append('YES' if tin[u] <= tin[v] <= tout[u] else 'NO')
print('\n'.join(out))

Đừng đếm sz bằng cách DFS lại từ mỗi đỉnh

Gọi một DFS riêng cho từng đỉnh để đếm cây con tốn $O(n^2)$, với cây đường thẳng $n = 2 \cdot 10^5$ là quá chậm. Một lần DFS từ gốc đã cho đủ $sz$, $dep$, $par$, $tin$, $tout$ của mọi đỉnh trong $O(n)$.

Phần 3Đường kính cây

Đường kính của cây là đường đi dài nhất giữa hai đỉnh. Thử mọi cặp đỉnh mất $O(n^2)$. Có một mẹo đẹp chỉ cần hai lần BFS (hoặc DFS):

Từ một đỉnh bất kỳ $s$ (ví dụ đỉnh 1), tìm đỉnh $a$ xa $s$ nhất.
Từ $a$, tìm đỉnh $b$ xa $a$ nhất. Đường đi $a \to b$ chính là một đường kính.

Đỉnh	1	2	3	4	5	6	7	8
khoảng cách từ 1	0	1	1	2	2	2	3	3
khoảng cách từ 7	3	2	4	3	1	5	0	2

Bảng 2. Lần 1 từ đỉnh 1: xa nhất là đỉnh 7 (hoà với 8, lấy chỉ số nhỏ). Lần 2 từ đỉnh 7: xa nhất là đỉnh 6, cách 5 cạnh. Đường kính dài 5.

Hình 2. Đường kính 7 – 5 – 2 – 1 – 3 – 6 (cạnh cam) dài 5. Đỉnh 7 là đỉnh $a$ tìm được ở lần BFS thứ nhất, đỉnh 6 là $b$.

Vì sao đúng? Mấu chốt là bổ đề: đỉnh $a$ xa $s$ nhất luôn là một đầu mút của một đường kính nào đó. Khi đã có điều này, lần BFS thứ hai từ $a$ đương nhiên tìm được đầu mút còn lại. Trực giác: hãy tưởng tượng cây làm bằng dây mềm, em cầm đỉnh $s$ nhấc lên; đỉnh treo thấp nhất là $a$. Một đường kính $x - y$ thì giống “sợi dây dài nhất” trong cây. Đi từ $s$ thật xa thì kiểu gì cũng chạy ra tới tận một đầu của sợi dây ấy.

Chứng minh ngắn (đọc thêm)

Gọi $x - y$ là một đường kính độ dài $D$. Đường từ $s$ tới $a$ và đường $x - y$ phải gặp nhau (nếu không, em nối chúng lại sẽ được đường dài hơn $D$, vô lý). Gọi $c$ là đỉnh trên đường $x - y$ mà đường $s \to a$ đi qua và rẽ đi, giả sử $y$ nằm phía ít nhất cũng xa như phía $x$ tính từ chỗ rẽ. Vì $a$ xa $s$ nhất nên $dist(s, a) \ge dist(s, y)$, bỏ phần chung $s \to c$ ở hai vế được $dist(c, a) \ge dist(c, y)$. Khi đó $dist(x, a) = dist(x, c) + dist(c, a) \ge dist(x, c) + dist(c, y) = D$. Không có đường nào dài hơn $D$, nên $x - a$ cũng là một đường kính, tức $a$ là đầu mút đường kính. Lập luận chỉ dùng việc trọng số cạnh không âm.

Xem code C++ / Python: đường kính cây bằng hai lần BFS, in cả đường đi (bấm để mở)

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

int n;
vector<int> adj[200005];
int d[200005], par[200005];

int bfs(int s){                         // tính d[] từ s, trả về đỉnh xa s nhất
    fill(d, d + n + 1, -1);
    queue<int> q;
    q.push(s); d[s] = 0; par[s] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : adj[u]) if(d[v] == -1){
            d[v] = d[u] + 1; par[v] = u; q.push(v);
        }
    }
    int far = 1;
    for(int i = 1; i <= n; i++) if(d[i] > d[far]) far = i;   // hoà thì lấy chỉ số nhỏ
    return far;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    int a = bfs(1);                     // lần 1: từ đỉnh bất kỳ
    int b = bfs(a);                     // lần 2: từ a, đỉnh xa nhất là b
    cout << d[b] << "\n";
    vector<int> path;
    for(int x = b; x != 0; x = par[x]) path.push_back(x);   // lần ngược b -> a
    reverse(path.begin(), path.end());
    for(int i = 0; i < (int)path.size(); i++) cout << path[i] << " \n"[i + 1 == (int)path.size()];
    return 0;
}

import sys
from collections import deque

def bfs(s):                         # trả về (đỉnh xa s nhất, d, par)
    d = [-1] * (n + 1); par = [0] * (n + 1)
    d[s] = 0
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1; par[v] = u; q.append(v)
    far = 1
    for i in range(1, n + 1):
        if d[i] > d[far]:           # hoà thì giữ chỉ số nhỏ
            far = i
    return far, d, par

data = sys.stdin.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
a, _, _ = bfs(1)                    # lần 1: từ đỉnh bất kỳ
b, d, par = bfs(a)                  # lần 2: từ a, đỉnh xa nhất là b
path = []
x = b
while x != 0:                       # lần ngược b -> a
    path.append(x); x = par[x]
print(d[b])
print(*path[::-1])

Cách thứ hai: quy hoạch động. Với mỗi đỉnh $u$, gọi $h[u]$ là độ dài đường dài nhất đi từ $u$ xuống một lá trong cây con của nó: $h[u] = \max(h[v] + w(u, v))$. Đường kính “gãy khúc” tại đỉnh cao nhất $u$ của nó, gồm hai nhánh xuống hai con khác nhau, nên đáp án $= \max_u$ (tổng hai giá trị $h[v] + w$ lớn nhất trong các con của $u$). Cách này chỉ cần một lần DFS và vẫn đúng khi cạnh có trọng số âm, trường hợp mà mẹo hai lần BFS bị sai.

Hai lần BFS chỉ đúng với trọng số không âm

Nếu đề cho cạnh có thể âm (ví dụ “lợi nhuận” mỗi đoạn đường), bổ đề ở trên không còn đúng. Khi đó dùng cách quy hoạch động $h[u]$. Còn với trọng số dương, hai lần BFS phải đổi thành hai lần DFS cộng dồn khoảng cách (BFS đếm số cạnh, không cộng trọng số), xem bài tập 3.

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

Kích thước cây con ở phần 2 đã là một bài QHĐ trên cây. Công thức chung: trạng thái gắn với một đỉnh $u$ (đáp án cho riêng cây con gốc $u$), tính từ trạng thái của các con, theo thứ tự từ lá lên gốc. Giống mọi bài QHĐ ở bài 19, khó nhất là chọn đúng trạng thái. Bài kinh điển nhất để luyện là:

Tập độc lập trọng số lớn nhất. Cây $n$ đỉnh, đỉnh $i$ có trọng số $w_i \ge 0$. Chọn một tập đỉnh sao cho không có hai đỉnh nào kề nhau (ví dụ: mời nhân viên dự tiệc, không mời cùng lúc sếp và nhân viên trực tiếp của sếp) để tổng trọng số lớn nhất.

Chỉ biết “đáp án tốt nhất của cây con gốc $u$” là chưa đủ: khi ghép lên cha, ta cần biết $u$ có bị chọn hay không, vì nếu $u$ được chọn thì cha của $u$ không được chọn. Vậy thêm một chiều trạng thái:

$dp[u][0]$: tổng lớn nhất trong cây con gốc $u$ khi không chọn $u$;
$dp[u][1]$: tổng lớn nhất trong cây con gốc $u$ khi có chọn $u$.

Chuyển trạng thái, với $v$ chạy qua các con của $u$:

$dp[u][0] = \sum_v \max(dp[v][0], dp[v][1]) \qquad dp[u][1] = w_u + \sum_v dp[v][0]$

Không chọn $u$ thì mỗi con được tự do, lấy trạng thái tốt hơn. Chọn $u$ thì mọi con bắt buộc không được chọn. Các cây con của những đứa con khác nhau không có cạnh nối nhau, nên chúng độc lập và ta được phép cộng đáp án lại. Lá: $dp[u][0] = 0$, $dp[u][1] = w_u$. Đáp án: $\max(dp[gốc][0], dp[gốc][1])$.

Đỉnh $u$ (thứ tự tính)	$w_u$	các con	$dp[u][0]$	$dp[u][1]$
7, 8, 4, 6 (lá)	2, 1, 4, 3	–	0	$w_u$
5	5	7, 8	max(0,2) + max(0,1) = 3	5 + 0 + 0 = 5
2	2	4, 5	max(0,4) + max(3,5) = 9	2 + 0 + 3 = 5
3	1	6	max(0,3) = 3	1 + 0 = 1
1 (gốc)	3	2, 3	max(9,5) + max(3,1) = 12	3 + 9 + 3 = 15

Bảng 3. Cây Hình 1 với trọng số $w = (3, 2, 1, 4, 5, 3, 2, 1)$. Đáp án $\max(12, 15) = 15$, tập được chọn là {1, 4, 5, 6}.

Bảng trên chỉ ghi kết quả. Em xem từng đỉnh được điền như thế nào, và cách truy vết ngược từ gốc xuống để biết chọn những đỉnh nào, trong mô phỏng sau (đổi trọng số tuỳ ý):

MÔ PHỎNGQHĐ trên cây: điền dp[u][0] | dp[u][1] từ lá lên gốcTập độc lập trọng số lớn nhất, gốc 1. Nhập cạnh và trọng số w[1..n] (tối đa 12 đỉnh).

Các cạnhTrọng số w

chưa tínhđang tínhcác con (đã có dp)đã tính / được chọn

Xem code C++ / Python: tập độc lập trọng số lớn nhất trên cây dp[u][0/1] (bấm để mở)

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

vector<int> adj[200005];
long long w[200005], dp[200005][2];

void dfs(int u, int p){
    dp[u][0] = 0;                       // không chọn u
    dp[u][1] = w[u];                    // chọn u
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);                      // tính xong con trước
        dp[u][0] += max(dp[v][0], dp[v][1]);   // u không chọn: con tự do
        dp[u][1] += dp[v][0];                  // u được chọn: con bắt buộc không chọn
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]);
    return 0;
}

import sys
sys.setrecursionlimit(10000)       # n lớn: xem cách khử đệ quy ở phần 5

def dfs(u, p):
    f0, f1 = 0, w[u]               # không chọn u / chọn u
    for v in adj[u]:
        if v == p:
            continue
        a, b = dfs(v, u)           # tính xong con trước
        f0 += max(a, b)            # u không chọn: con tự do
        f1 += a                    # u được chọn: con bắt buộc không chọn
    return f0, f1

data = sys.stdin.read().split()
n = int(data[0])
w = [0] + [int(x) for x in data[1:n + 1]]
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[n + 1 + 2 * i]), int(data[n + 2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
print(max(dfs(1, 0)))

Khuôn mẫu QHĐ trên cây

1. Trạng thái $dp[u][\ldots]$ = đáp án cho cây con gốc $u$, kèm thêm thông tin về chính đỉnh $u$ mà cha cần biết (chọn hay không, màu gì, đã ghép cặp chưa…).
2. Gom các con lần lượt từng con một: các cây con rời nhau nên cộng (bài max/min) hoặc nhân (bài đếm) kết quả lại.
3. Tính trong DFS sau khi các con trả về (hoặc duyệt ngược thứ tự BFS, xem phần 5). Mỗi cạnh được xét một lần nên tổng $O(n \times \text{số trạng thái})$.

Biến thể đếm. Đổi “max” thành “đếm số cách” là ra bài: có bao nhiêu cách tô đen một số đỉnh sao cho không có hai đỉnh đen kề nhau. Gọi $f[u][0]$, $f[u][1]$ là số cách tô cây con gốc $u$ khi $u$ trắng / đen. Các cây con độc lập nên ta nhân số cách (quy tắc nhân, như ở bài 26):

$f[u][0] = \prod_v (f[v][0] + f[v][1]) \qquad f[u][1] = \prod_v f[v][0]$

Lá có $f = (1, 1)$. Với cây Hình 1: $f[5] = (4, 1)$, $f[2] = (2 \cdot 5, 1 \cdot 4) = (10, 4)$, $f[3] = (2, 1)$, $f[1] = (14 \cdot 3, 10 \cdot 2) = (42, 20)$, tổng cộng 62 cách. Nhớ lấy modulo sau mỗi phép nhân khi đáp án lớn.

Lỗi hay gặp

Quên trạng thái của đỉnh $u$: chỉ lưu $dp[u]$ một chiều rồi loay hoay không biết cha có được chọn không. Hãy tự hỏi “cha cần biết gì về $u$?” rồi đưa đúng thông tin đó vào trạng thái.
Tràn số: tổng trọng số tới $2 \cdot 10^5 \cdot 10^9$ phải dùng long long.
Duyệt cả cha như một đứa con: thiếu dòng if(v == p) continue; thì đệ quy chạy qua lại giữa hai đỉnh mãi mãi.

Phần 5Đổi gốc và khử đệ quy

Bài toán. Với mỗi đỉnh $u$, tính $ans[u] = \sum_v dist(u, v)$, tổng khoảng cách từ $u$ tới mọi đỉnh. Chạy BFS từ từng đỉnh mất $O(n^2)$. Kỹ thuật đổi gốc (rerooting) làm trong $O(n)$ với hai lần duyệt:

Lần 1 (từ dưới lên), gốc 1: tính $sz[v]$ và $ans[1] = \sum_v dep[v]$.
Lần 2 (từ trên xuống): biết $ans$ của cha $p$, suy ra $ans$ của con $v$ trong $O(1)$.

Khi dời gốc từ $p$ xuống con $v$ qua cạnh $(p, v)$: $sz[v]$ đỉnh trong cây con gốc $v$ đều gần thêm 1, còn $n - sz[v]$ đỉnh còn lại đều xa thêm 1. Vậy:

$ans[v] = ans[p] - sz[v] + (n - sz[v])$

Với cây Hình 1: $ans[1] = 0 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 14$; $ans[2] = 14 - 5 + 3 = 12$; $ans[3] = 14 - 2 + 6 = 18$; $ans[5] = 12 - 3 + 5 = 14$… Em bấm từng bước để thấy phần xanh lá (gần thêm) và phần đỏ (xa thêm) mỗi lần dời gốc:

MÔ PHỎNGĐổi gốc: tổng khoảng cách từ mỗi đỉnh tới mọi đỉnhNhập cạnh (tối đa 12 đỉnh) và gốc ban đầu. Mỗi bước dời gốc qua một cạnh, chỉ mất O(1).

Các cạnhGốc ban đầu

gốc cũ pcây con của đỉnh mới: gần thêm 1phần còn lại: xa thêm 1chưa tính ans

Khuôn mẫu đổi gốc

Bước 1: chọn gốc tạm, tính $down[u]$ = đáp án chỉ xét cây con gốc $u$ (DFS từ dưới lên).
Bước 2: đi từ trên xuống, “đẩy” phần thông tin phía trên cha (ngoài cây con của $v$) xuống cho con $v$: $ans[v]$ = kết hợp($down[v]$, phần phía trên). Ở bài tổng khoảng cách, phần phía trên gói gọn trong công thức $-sz[v] + (n - sz[v])$; ở bài khó hơn có thể cần thêm giá trị lớn nhất / lớn nhì của các con (bài tập 7, 8).

Khử đệ quy. Đề HSG hay cho $n = 2 \cdot 10^5$ và cố tình cho cây là một đường thẳng 1 – 2 – 3 – … – $n$. DFS đệ quy khi đó sâu $2 \cdot 10^5$ tầng:

Python: mặc định chỉ cho đệ quy khoảng 1000 tầng. Tăng sys.setrecursionlimit(10**6) thì hết báo lỗi RecursionError nhưng ngăn xếp thật của chương trình vẫn tràn, chương trình chết đột ngột không in gì cả (thường thấy là lỗi Runtime Error hoặc segmentation fault).
C++: mỗi tầng tốn vài chục byte, $2 \cdot 10^5$ tầng tốn vài MB. Trên Linux (Codeforces, VNOJ) thường ổn, nhưng một số máy chấm chạy Windows chỉ cho ngăn xếp 1–8 MB nên vẫn có thể tràn.

Cách chữa gọn nhất: lấy thứ tự BFS từ gốc. Trong thứ tự này, cha luôn đứng trước con. Vì vậy:

duyệt ngược thứ tự BFS = con luôn được xử lý trước cha → dùng cho thông tin từ dưới lên ($sz$, $dp$);
duyệt xuôi thứ tự BFS = cha luôn được xử lý trước con → dùng cho thông tin từ trên xuống ($dep$, đổi gốc).

Không cần ngăn xếp, không cần đệ quy, mỗi vòng chỉ là một vòng for. Code dưới đây giải trọn bài tổng khoảng cách bằng đúng cách đó:

Xem code C++ / Python: đổi gốc tính tổng khoảng cách, không đệ quy (bấm để mở)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    // 1) Thứ tự BFS từ gốc 1: cha luôn đứng TRƯỚC con. Không đệ quy.
    vector<int> order, par(n + 1, 0), dep(n + 1, 0);
    order.push_back(1);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(int v : adj[u]) if(v != par[u]){
            par[v] = u; dep[v] = dep[u] + 1; order.push_back(v);
        }
    }
    // 2) Duyệt NGƯỢC thứ tự: con xong trước cha -> tính sz từ lá lên
    vector<long long> sz(n + 1, 1), ans(n + 1, 0);
    for(int i = n - 1; i > 0; i--) sz[par[order[i]]] += sz[order[i]];
    for(int v = 1; v <= n; v++) ans[1] += dep[v];
    // 3) Duyệt XUÔI thứ tự: cha có ans trước con -> đổi gốc từ cha xuống con
    for(int i = 1; i < n; i++){
        int v = order[i];
        ans[v] = ans[par[v]] - sz[v] + (n - sz[v]);
    }
    for(int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
# 1) Thứ tự BFS từ gốc 1: cha luôn đứng TRƯỚC con. Không đệ quy.
par = [0] * (n + 1); dep = [0] * (n + 1)
order = [1]
for u in order:                      # list dài thêm trong lúc duyệt: chính là BFS
    for v in adj[u]:
        if v != par[u]:
            par[v] = u; dep[v] = dep[u] + 1; order.append(v)
# 2) Duyệt NGƯỢC thứ tự: con xong trước cha -> tính sz từ lá lên
sz = [1] * (n + 1)
for v in reversed(order[1:]):
    sz[par[v]] += sz[v]
ans = [0] * (n + 1)
ans[1] = sum(dep)
# 3) Duyệt XUÔI thứ tự: cha có ans trước con -> đổi gốc từ cha xuống con
for v in order[1:]:
    ans[v] = ans[par[v]] - sz[v] + (n - sz[v])
print(*ans[1:])

Việc cần làm	Đệ quy	Không đệ quy (thứ tự BFS)
Thông tin từ trên xuống: $dep$, $dist$ từ gốc, đổi gốc	tính trước khi gọi `dfs(v, u)`	duyệt xuôi `order`
Thông tin từ dưới lên: $sz$, $dp[u][0/1]$, $h[u]$	tính sau khi `dfs(v, u)` trả về	duyệt ngược `order`
Thứ tự tin/tout liên tiếp trên cây con	tự nhiên	cần ngăn xếp tự cài (DFS lặp)
Độ sâu cây tối đa an toàn	Python ~ vài nghìn, C++ ~ $10^5$ (tuỳ máy)	không giới hạn

Bảng 4. Chuyển một lời giải đệ quy trên cây sang dạng vòng lặp. Thứ tự BFS không cho tin/tout liên tiếp, khi cần trải cây phải mô phỏng DFS bằng ngăn xếp.

Mẹo cho Python khi buộc phải đệ quy

Nếu thật sự muốn giữ đệ quy, có thể chạy hàm chính trong một luồng có ngăn xếp lớn: threading.stack_size(1 << 26) rồi threading.Thread(target=main).start(), kèm sys.setrecursionlimit(10**6). Tuy vậy cách này chậm và không phải máy chấm nào cũng cho phép. Thói quen tốt nhất khi đi thi: viết dạng thứ tự BFS ngay từ đầu. Toàn bộ lời giải Python ở phần bài tập đều viết như vậy.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

Software (SOFTWARE) (Olympic 30/4 2023 – Tin học khối 10) (Trung bình)
Bữa Tiệc (BUATIEC) (HSG12 Lâm Đồng 2025 – Bài 4) (Trung bình)
Công Ty (HSG12 Hà Nội 2023 Vòng 1 – Bài 4) (Khó)
Count Ways to Build Rooms in an Ant Colony (LeetCode 1916) (Khó)
Smallest Missing Genetic Value in Each Subtree (LeetCode 2003) (Khó)

Xem toàn bộ bài cùng chủ đề: nhãn Cây.

Bài tậpLuyện cây và QHĐ trên cây

Bài 1Lá và chiều caoDễ

Cho cây $n$ đỉnh ($1 \le n \le 2 \cdot 10^5$) gốc 1, dòng tiếp theo là $n - 1$ cạnh $u\ v$. Hãy in số lá (đỉnh không có con) và chiều cao của cây (độ sâu lớn nhất, gốc có độ sâu 0). Với $n = 1$, gốc không có con nên cũng là lá.

Input

Output

4 3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Duyệt BFS từ gốc 1 để có cha và độ sâu. Đỉnh $u$ là lá khi nó không có con, tức là mọi đỉnh kề của nó đều là cha: số đỉnh kề của $u$ bằng 1 với $u \ne$ gốc (gốc là lá chỉ khi $n = 1$). Cây Hình 1 có 4 lá 4, 6, 7, 8 và độ sâu lớn nhất là 3 (đỉnh 7, 8).

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<int> order = {1}, par(n + 1, 0), dep(n + 1, 0);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(int v : adj[u]) if(v != par[u]){
            par[v] = u; dep[v] = dep[u] + 1; order.push_back(v);
        }
    }
    int leaves = 0, h = 0;
    for(int u = 1; u <= n; u++){
        int children = (int)adj[u].size() - (u == 1 ? 0 : 1);
        if(children == 0) leaves++;
        h = max(h, dep[u]);
    }
    cout << leaves << " " << h;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1); dep = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != par[u]:
            par[v] = u; dep[v] = dep[u] + 1; order.append(v)
leaves = sum(1 for u in range(1, n + 1) if len(adj[u]) - (0 if u == 1 else 1) == 0)
print(leaves, max(dep))

Bài 2Số cấp dướiDễ

Công ty có $n$ nhân viên ($1 \le n \le 2 \cdot 10^5$), nhân viên 1 là giám đốc. Với $i = 2, \ldots, n$, sếp trực tiếp của nhân viên $i$ là $p_i$ ($p_i < i$). Với mỗi nhân viên, hãy đếm số người dưới quyền (trực tiếp hoặc gián tiếp).

Input: dòng 1 là $n$, dòng 2 là $n - 1$ số $p_2, \ldots, p_n$. Output: $n$ số trên một dòng.

Input

8
1 1 2 2 3 5 5

Output

7 4 1 0 2 0 0 0

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Số người dưới quyền của $i$ là $sz[i] - 1$. Điều kiện $p_i < i$ cho sẵn một thứ tự “cha trước con”: chỉ cần duyệt $i$ từ $n$ về 2 và làm sz[p[i]] += sz[i], không cần dựng danh sách kề, không cần DFS. Ví dụ đúng là cây Hình 1: giám đốc có 7 người dưới quyền, nhân viên 2 có 4 người (4, 5, 7, 8).

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> p(n + 1, 0), sz(n + 1, 1);
    for(int i = 2; i <= n; i++) cin >> p[i];
    for(int i = n; i >= 2; i--) sz[p[i]] += sz[i];   // con có chỉ số lớn hơn cha
    for(int i = 1; i <= n; i++) cout << sz[i] - 1 << " \n"[i == n];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0, 0] + [int(x) for x in data[1:n]]
sz = [1] * (n + 1)
for i in range(n, 1, -1):          # con có chỉ số lớn hơn cha
    sz[p[i]] += sz[i]
print(*[s - 1 for s in sz[1:]])

Bài 3Đường kính có trọng sốTrung bình

Cho cây $n$ đỉnh ($2 \le n \le 2 \cdot 10^5$), mỗi cạnh $u\ v\ w$ có độ dài $w$ ($1 \le w \le 10^9$). Tìm độ dài đường đi dài nhất giữa hai đỉnh của cây.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Hai lần duyệt như phần 3, nhưng khoảng cách phải cộng trọng số: $dist[v] = dist[u] + w$ (thứ tự duyệt nào cũng được, vì trên cây đường đi là duy nhất). Lần 1 từ đỉnh 1 tìm đỉnh xa nhất $a$, lần 2 từ $a$ lấy khoảng cách lớn nhất. Đáp án tới $2 \cdot 10^{14}$ nên dùng long long. Đường dài nhất là 5 – 2 – 1 – 3 – 6 dài $6 + 3 + 4 + 1 = 14$.

Xem code tham khảo (C++ / Python)

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

int n;
vector<vector<pair<int, int>>> adj;

vector<long long> distFrom(int s){
    vector<long long> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while(!st.empty()){
        int u = st.back(); st.pop_back();
        for(auto [v, w] : adj[u]) if(d[v] < 0){
            d[v] = d[u] + w; st.push_back(v);
        }
    }
    return d;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    adj.assign(n + 1, {});
    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w}); adj[v].push_back({u, w});
    }
    vector<long long> d = distFrom(1);
    int a = max_element(d.begin() + 1, d.end()) - d.begin();
    d = distFrom(a);
    cout << *max_element(d.begin() + 1, d.end());
    return 0;
}

import sys

def dist_from(s):
    d = [-1] * (n + 1)
    d[s] = 0
    st = [s]
    while st:
        u = st.pop()
        for v, w in adj[u]:
            if d[v] < 0:
                d[v] = d[u] + w
                st.append(v)
    return d

data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v, w = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
    adj[u].append((v, w)); adj[v].append((u, w))
d = dist_from(1)
a = max(range(1, n + 1), key=lambda x: d[x])
print(max(dist_from(a)))

Bài 4Vùng đất giá trị nhấtTrung bình

Vương quốc có $n$ thành phố ($1 \le n \le 2 \cdot 10^5$) nối bằng $n - 1$ con đường tạo thành cây. Thành phố $i$ có giá trị $a_i$ ($|a_i| \le 10^9$, có thể âm). Hãy chọn một tập thành phố khác rỗng và liên thông (đi lại được với nhau chỉ qua các thành phố trong tập) có tổng giá trị lớn nhất.

Input: $n$; dòng 2 là $a_1, \ldots, a_n$; tiếp theo $n - 1$ cạnh.

Input

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

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Gọi $dp[u]$ là tổng lớn nhất của một tập liên thông có chứa $u$ và nằm trong cây con gốc $u$. Mỗi con $v$ hoặc bị bỏ, hoặc góp vào một tập liên thông chứa $v$: $dp[u] = a_u + \sum_v \max(0, dp[v])$. Tập tốt nhất của cả cây có một đỉnh “cao nhất” $u$, nên đáp án $= \max_u dp[u]$. Ví dụ: $dp[6] = -2 + 6 = 4$, $dp[3] = 4 + 4 = 8$, $dp[2] = -5 + 0 + 2 = -3$ (bị bỏ), $dp[1] = 3 + 0 + 8 = 11$: chọn {1, 3, 6, 7}.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> dp(n + 1);
    for(int i = 1; i <= n; i++) cin >> dp[i];       // khởi tạo dp[u] = a[u]
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<int> order = {1}, par(n + 1, 0);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(int v : adj[u]) if(v != par[u]){ par[v] = u; order.push_back(v); }
    }
    long long ans = LLONG_MIN;
    for(int i = n - 1; i >= 0; i--){                // con trước, cha sau
        int u = order[i];
        ans = max(ans, dp[u]);                      // dp[u] đã gom đủ các con
        if(par[u] && dp[u] > 0) dp[par[u]] += dp[u];
    }
    cout << ans;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
dp = [0] + [int(x) for x in data[1:n + 1]]       # khởi tạo dp[u] = a[u]
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[n + 1 + 2 * i]), int(data[n + 2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != par[u]:
            par[v] = u; order.append(v)
ans = None
for u in reversed(order):                         # con trước, cha sau
    if ans is None or dp[u] > ans:
        ans = dp[u]
    if par[u] and dp[u] > 0:
        dp[par[u]] += dp[u]
print(ans)

Bài 5Đếm vùng liên thôngTrung bình

Cho cây $n$ đỉnh ($1 \le n \le 2 \cdot 10^5$). Đếm số tập đỉnh khác rỗng và liên thông (cây con theo nghĩa “mảnh cây”) theo modulo $10^9 + 7$.

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Gọi $g[u]$ là số tập liên thông có đỉnh cao nhất đúng là $u$ (chứa $u$, nằm trong cây con gốc $u$). Với mỗi con $v$: hoặc không lấy gì bên nhánh $v$ (1 cách), hoặc lấy một tập liên thông chứa $v$ ($g[v]$ cách). Các nhánh độc lập nên nhân: $g[u] = \prod_v (1 + g[v])$. Mỗi tập liên thông có đúng một đỉnh cao nhất, nên đáp án $= \sum_u g[u]$. Ví dụ: $g[3] = g[4] = 1$, $g[2] = 2 \cdot 2 = 4$, $g[1] = 1 + 4 = 5$, tổng 11 (4 tập 1 đỉnh, 3 tập 2 đỉnh, 3 tập 3 đỉnh, 1 tập 4 đỉnh).

Xem code tham khảo (C++ / Python)

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

const long long MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<int> order = {1}, par(n + 1, 0);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(int v : adj[u]) if(v != par[u]){ par[v] = u; order.push_back(v); }
    }
    vector<long long> g(n + 1, 1);
    long long ans = 0;
    for(int i = n - 1; i >= 0; i--){
        int u = order[i];                      // g[u] đã nhân đủ (1 + g[con])
        ans = (ans + g[u]) % MOD;
        if(par[u]) g[par[u]] = g[par[u]] * (1 + g[u]) % MOD;
    }
    cout << ans;
    return 0;
}

import sys

MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != par[u]:
            par[v] = u; order.append(v)
g = [1] * (n + 1)
ans = 0
for u in reversed(order):                  # g[u] đã nhân đủ (1 + g[con])
    ans = (ans + g[u]) % MOD
    if par[u]:
        g[par[u]] = g[par[u]] * (1 + g[u]) % MOD
print(ans)

Bài 6Ghép cặp tối đaKhá

Có $n$ học sinh ($1 \le n \le 2 \cdot 10^5$) và $n - 1$ cặp quen nhau tạo thành một cây. Thầy muốn chia càng nhiều cặp đôi càng tốt, mỗi cặp gồm hai bạn quen nhau, mỗi bạn thuộc nhiều nhất một cặp. Hỏi chia được tối đa bao nhiêu cặp?

Input

Output

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Trạng thái của đỉnh $u$ mà cha cần biết: $u$ đã được ghép với một con hay chưa. $dp[u][0]$ = số cặp lớn nhất trong cây con khi $u$ chưa ghép (còn rảnh để ghép với cha): $dp[u][0] = \sum_v \max(dp[v][0], dp[v][1])$. $dp[u][1]$ = khi $u$ ghép với đúng một con $v$: thay phần của $v$ bằng $dp[v][0] + 1$, tức $dp[u][1] = \max_v \big(dp[u][0] - \max(dp[v][0], dp[v][1]) + dp[v][0] + 1\big)$. Ở cây Hình 1, hai lá 7 và 8 cùng chỉ quen 5 nên không thể ghép đủ 4 cặp; 3 cặp ví dụ là (2, 4), (5, 7), (3, 6).

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<int> order = {1}, par(n + 1, 0);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(int v : adj[u]) if(v != par[u]){ par[v] = u; order.push_back(v); }
    }
    vector<int> f0(n + 1, 0), f1(n + 1, 0);
    for(int i = n - 1; i >= 0; i--){
        int u = order[i];
        int bestGain = INT_MIN;                 // lợi thêm khi ghép u với một con
        for(int v : adj[u]) if(v != par[u]){
            f0[u] += max(f0[v], f1[v]);
            bestGain = max(bestGain, f0[v] + 1 - max(f0[v], f1[v]));
        }
        f1[u] = (bestGain == INT_MIN) ? INT_MIN / 2 : f0[u] + bestGain;   // lá không ghép được với con
    }
    cout << max(f0[1], f1[1]);
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
par = [0] * (n + 1)
order = [1]
for u in order:
    for v in adj[u]:
        if v != par[u]:
            par[v] = u; order.append(v)
NEG = -10**9
f0 = [0] * (n + 1); f1 = [NEG] * (n + 1)
for u in reversed(order):
    gain = NEG                            # lợi thêm khi ghép u với một con
    for v in adj[u]:
        if v != par[u]:
            m = max(f0[v], f1[v])
            f0[u] += m
            gain = max(gain, f0[v] + 1 - m)
    if gain > NEG:
        f1[u] = f0[u] + gain
print(max(f0[1], f1[1]))

Bài 7Xa nhất từ mỗi đỉnhKhá

Cho cây $n$ đỉnh ($1 \le n \le 2 \cdot 10^5$, mỗi cạnh dài 1). Với mỗi đỉnh $u$, in khoảng cách lớn nhất từ $u$ tới một đỉnh khác (với $n = 1$ in 0).

Input

Output

3 3 4 4 4 5 5 5

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dùng bổ đề ở phần 3 theo chiều ngược lại: với mọi đỉnh $u$, đỉnh xa $u$ nhất có thể chọn là một trong hai đầu mút $a$, $b$ của một đường kính. Vậy chỉ cần ba lần BFS: tìm $a$, tính $d_a$ từ $a$ (cũng tìm được $b$), tính $d_b$ từ $b$, rồi đáp án của $u$ là $\max(d_a[u], d_b[u])$. Ở cây Hình 1, $a = 7$, $b = 6$: đỉnh 2 có $\max(2, 3) = 3$. (Bài này cũng giải được bằng đổi gốc với cặp “dài nhất, dài nhì” của các con, em thử làm thêm.)

Xem code tham khảo (C++ / Python)

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

int n;
vector<vector<int>> adj;

vector<int> bfs(int s){
    vector<int> d(n + 1, -1), q = {s};
    d[s] = 0;
    for(int i = 0; i < (int)q.size(); i++){
        int u = q[i];
        for(int v : adj[u]) if(d[v] < 0){ d[v] = d[u] + 1; q.push_back(v); }
    }
    return d;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    adj.assign(n + 1, {});
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    vector<int> d1 = bfs(1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    vector<int> da = bfs(a);
    int b = max_element(da.begin() + 1, da.end()) - da.begin();
    vector<int> db = bfs(b);
    for(int u = 1; u <= n; u++) cout << max(da[u], db[u]) << " \n"[u == n];
    return 0;
}

import sys

def bfs(s):
    d = [-1] * (n + 1)
    d[s] = 0
    q = [s]
    for u in q:
        for v in adj[u]:
            if d[v] < 0:
                d[v] = d[u] + 1
                q.append(v)
    return d

data = sys.stdin.buffer.read().split()
n = int(data[0])
adj = [[] for _ in range(n + 1)]
for i in range(n - 1):
    u, v = int(data[1 + 2 * i]), int(data[2 + 2 * i])
    adj[u].append(v); adj[v].append(u)
d1 = bfs(1)
a = max(range(1, n + 1), key=lambda x: d1[x])
da = bfs(a)
b = max(range(1, n + 1), key=lambda x: da[x])
db = bfs(b)
print(*[max(da[u], db[u]) for u in range(1, n + 1)])

Bài 8Đặt kho hàngKhó

Có $n$ thị trấn ($1 \le n \le 10^5$) nối bằng $n - 1$ con đường tạo thành cây, đường $u\ v\ w$ dài $w$ ($1 \le w \le 1000$). Thị trấn $i$ cần $c_i$ chuyến hàng ($0 \le c_i \le 1000$). Nếu đặt kho ở thị trấn $u$, chi phí là $\sum_i c_i \cdot dist(u, i)$. Hãy in thị trấn đặt kho có chi phí nhỏ nhất (nếu nhiều thị trấn bằng nhau, in chỉ số nhỏ nhất) và chi phí đó.

Input: $n$; dòng 2 là $c_1, \ldots, c_n$; tiếp theo $n - 1$ dòng $u\ v\ w$.

Input

Output

3 28

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đổi gốc như phần 5 nhưng “đếm đỉnh” thay bằng “đếm chuyến hàng” và mỗi cạnh có độ dài. Gọi $C[v]$ = tổng $c$ trong cây con gốc $v$, $T$ = tổng mọi $c_i$. Dời kho từ cha $p$ xuống con $v$ qua cạnh dài $w$: $C[v]$ chuyến hàng gần thêm $w$, $T - C[v]$ chuyến xa thêm $w$, nên $ans[v] = ans[p] + w \cdot (T - 2C[v])$. $ans[1] = \sum c_i \cdot dist(1, i)$ tính ở lần duyệt đầu. Chi phí tới $10^{8} \cdot 10^{8} = 10^{16}$ nên dùng long long. Ví dụ: $ans[1] = 33$, $ans[3] = 33 + 1 \cdot (11 - 2 \cdot 8) = 28$ là nhỏ nhất.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> C(n + 1), dist(n + 1, 0), ans(n + 1, 0);
    long long T = 0;
    for(int i = 1; i <= n; i++){ cin >> C[i]; T += C[i]; }
    vector<vector<pair<int, int>>> adj(n + 1);
    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w}); adj[v].push_back({u, w});
    }
    vector<int> order = {1}, par(n + 1, 0), pw(n + 1, 0);
    for(int i = 0; i < (int)order.size(); i++){
        int u = order[i];
        for(auto [v, w] : adj[u]) if(v != par[u]){
            par[v] = u; pw[v] = w; dist[v] = dist[u] + w; order.push_back(v);
        }
    }
    for(int u = 1; u <= n; u++) ans[1] += C[u] * dist[u];        // c[u] gốc, trước khi gom
    for(int i = n - 1; i > 0; i--) C[par[order[i]]] += C[order[i]];   // C = tổng cây con
    int best = 1;
    for(int i = 1; i < n; i++){
        int v = order[i];
        ans[v] = ans[par[v]] + (long long)pw[v] * (T - 2 * C[v]);
    }
    for(int v = 2; v <= n; v++) if(ans[v] < ans[best]) best = v;
    cout << best << " " << ans[best];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
C = [0] + [int(x) for x in data[1:n + 1]]
T = sum(C)
adj = [[] for _ in range(n + 1)]
pos = n + 1
for _ in range(n - 1):
    u, v, w = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
    adj[u].append((v, w)); adj[v].append((u, w))
par = [0] * (n + 1); pw = [0] * (n + 1); dist = [0] * (n + 1)
order = [1]
for u in order:
    for v, w in adj[u]:
        if v != par[u]:
            par[v] = u; pw[v] = w; dist[v] = dist[u] + w; order.append(v)
ans = [0] * (n + 1)
ans[1] = sum(C[u] * dist[u] for u in range(1, n + 1))   # c[u] gốc, trước khi gom
for v in reversed(order[1:]):                             # C = tổng cây con
    C[par[v]] += C[v]
for v in order[1:]:
    ans[v] = ans[par[v]] + pw[v] * (T - 2 * C[v])
best = min(range(1, n + 1), key=lambda u: (ans[u], u))
print(best, ans[best])

Bài tiếp theo · Bài 34

LCA và kỹ thuật nhảy nhị phân

Tìm tổ tiên chung gần nhất của hai đỉnh, khoảng cách giữa hai đỉnh bất kỳ trên cây chỉ trong $O(\log n)$ mỗi truy vấn, nhờ bảng “nhảy $2^k$ bước”.

Học bài 34 →

← Bài 32: Tổng ôn Thuật toán nâng cao Xem cả series Thuật toán chuyên sâu

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 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!

Lập Trình Thuật Toán

Bài 33: Cây và quy hoạch động trên cây trong C++ và Python: DFS trên cây, kích thước cây con, đường kính, tập độc lập lớn nhất, kỹ thuật đổi gốc

Lời mở đầu

Phần 1Cây có gốc và DFS truyền cha

Phần 2Kích thước cây con và thứ tự duyệt

Phần 3Đường kính cây

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

Phần 5Đổi gốc và khử đệ quy

Bài tậpLuyện cây và QHĐ trên cây

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++