Cấu trúc dữ liệu Cây🌳 (🚧)
1. Khái niệm về cây
- Trong lý thuyết đồ thị, cây có các thuộc tính sau:
- Là một đồ thị vô hướng gồm $V$ đỉnh và $V-1$ cạnh
- Liên thông
- Không có chu trình
- Giữa hai đỉnh bất kỳ trong cây luôn có duy nhất một đường đi đơn.
- Nếu thêm một cạnh bất kỳ vào cây, ta sẽ tạo ra đúng một chu trình.
- Nếu xóa đi một cạnh bất kỳ, đồ thị sẽ mất tính liên thông trở thành một Rừng - Forest.
Trong CP, cách tối ưu và phổ biến nhất để biểu diễn cây là sử dụng Danh sách kề (Adjacency List).
2. Duyệt cây và Tính toán thông số cơ bản
Thuật toán Tìm kiếm theo chiều sâu (DFS) là “xương sống” của hầu hết các bài toán về cây. Thông qua một lần chạy DFS, ta có thể lấy được các thông tin quan trọng của mỗi đỉnh:
- depth[u] hay dist[u]: Độ sâu của đỉnh u (khoảng cách từ gốc).
- sz[u]: Kích thước cây con gốc u (số lượng đỉnh nằm trong nhánh của u).
- parent[u]: Cha trực tiếp của u.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int limN = 1e5 + 5;
vector<int> adj[limN];
int dist[limN]; // khởi tạo -1 (unvisited)
int sz[limN];
int parent[limN]; // khởi tạo -1 nghĩa chưa có cha
// gọi hàm: dfs(root, 0)
void dfs(int u, int p) {
sz[u] = 1;
parent[u] = p;
for (const int &v : adj[u]) {
if (v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
}
3. Đường kính của Cây (Tree Diameter)
Đường kính của cây là đường đi dài nhất giữa hai đỉnh bất kỳ. Thuật toán tối ưu nhất là dùng 2 lần DFS/BFS:
- Bắt đầu DFS từ đỉnh bất kỳ (ví dụ đỉnh 1), tìm đỉnh $A$ xa nhất.
- Bắt đầu DFS từ đỉnh $A$, tìm đỉnh $B$ xa nhất. Khoảng cách từ $A$ đến $B$ chính là đường kính của cây.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int limN = 1e5 + 5;
vector<int> adj[limN];
int dist[limN];
void dfs(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
int get_diameter(int n) {
// bước 1: tìm đỉnh u sâu nhất
dist[1] = 0;
dfs(1, 0);
int u = 1;
FOR(i, 1, n + 1) {
if (dist[i] > dist[u]) u = i;
}
// bước 2: Tìm đỉnh v xa đỉnh u nhất
dist[u] = 0;
dfs(u, 0);
int v = u;
FOR(i, 1, n + 1) {
if (dist[i] > dist[v]) v = i;
}
return dist[v]; // dist[v] là đường kính
}
Các dấu hiệu nhận biết
- Khoảng cách xa nhất: “Tìm khoảng cách lớn nhất giữa 2 đỉnh bất kỳ”, “Tìm hai thành phố cách nhau xa nhất”.
- Tối ưu hóa vị trí (Min-Max): “Tìm một đỉnh sao cho khoảng cách từ nó đến đỉnh xa nhất là nhỏ nhất” (Đây là bài toán tìm Bán kính/Tâm của cây - liên quan trực tiếp đến đường kính).
- Gộp/Tách cây: “Nối thêm một cạnh giữa 2 cây sao cho đường kính cây mới là nhỏ nhất/lớn nhất”.
- Đặc điểm hình học: Đề bài đề cập đến việc “đi xuyên qua” toàn bộ cấu trúc cây từ đầu này sang đầu kia.
Các dạng bài tiêu biểu:
- Tìm tâm cây (Tree Center): Đỉnh nằm chính giữa đường kính.
- Cập nhật động: Cho một cây, mỗi bước thêm một đỉnh, hỏi đường kính mới là bao nhiêu.
- Đường kính trên nhánh: Với mỗi đỉnh $i$, hãy tìm khoảng cách từ $i$ đến đỉnh xa nó nhất.
4. Binary Lifting & LCA
Binary Lifting là một kỹ thuật biến việc nhảy từng bước một ($O(N)$) thành việc nhảy theo các lũy thừa của 2 ($O(log N)$).
Hầu hết các bài toán thao tác trên đường đi giữa 2 đỉnh $(u, v)$ đều cần dùng LCA.
Kỹ thuật: Nhảy nhị phân (Binary Lifting)
- Độ phức tạp: Khởi tạo $\mathcal{O}(N \log N)$, Truy vấn $\mathcal{O}(\log N)$.
- Ý tưởng: Mảng up[u][j] lưu tổ tiên thứ $2^j$ của đỉnh $u$.
- Công thức truy hồi:
- Khoảng cách giữa 2 đỉnh u và v trên cây có thể tính nhanh bằng công thức:
(Kết hợp Mảng cộng dồn trên cây (Tree Prefix Sum) để tính tổng/max/min trên đường đi từ $u$ đến $v$.)
a, Tổ tiên thứ k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n, q;
const int limN = 2e5 + 5;
const int limLOG = 20 + 1; //2^20 cho N <= 1e6
vector<int> adj[limN];
int up[limN][limLOG];
int dist[limN];
// DFS để tính dist và tổ tiên trực tiếp (2^0)
void dfs(int u, int p) {
up[u][0] = p;
FOR(j, 1, limLOG) {
// tổ tiên thứ 2^j của i là tổ tiên thứ 2^(j-1) của (tổ tiên thứ 2^(j-1) của i)
up[u][j] = up[up[u][j - 1]][j - 1];
}
for(const int &v: adj[u]) {
if(v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
int get_kth(int u, int k) {
if(dist[u] < k) return -1; // nếu k lớn hơn độ sâu của u thì không có tổ tiên bậc k
FOR(j, 0, limLOG) {
if(bit(k, j)) u = up[u][j];
}
return u;
}
int main(void) {
cin >> n >> q;
FOR(u, 2, n + 1) {
int boss; cin >> boss;
adj[boss].eb(u);
}
// init
dfs(1, 0);
while(q--) {
int x, k; cin >> x >> k;
cout << get_kth(x, k) << nl;
}
}
b, LCA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n, q;
const int limN = 2e5 + 5;
const int limLOG = 21;
vector<int> adj[limN];
int dist[limN];
int up[limN][limLOG];
void dfs(int u, int p) {
up[u][0] = p;
FOR(j, 1, limLOG) {
up[u][j] = up[up[u][j - 1]][j - 1];
}
for(const int &v: adj[u]) {
if(v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
int get_kth(int u, int k) {
for(int j = limLOG - 1; j >= 0; j--) {
if(bit(k, j)) u = up[u][j];
}
return u;
}
int get_lca(int u, int v) {
if(dist[u] < dist[v]) swap(u, v); // u luôn có độ sâu lớn hơn
u = get_kth(u, dist[u] - dist[v]); // đưa u và v về cùng 1 độ sâu
if(u == v) return u; // pruning
for(int j = limLOG - 1; j >= 0; j--) {
if(up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
int main(void) {
cin >> n >> q;
FOR(u, 2, n + 1) {
int boss; cin >> boss;
adj[boss].eb(u);
}
dfs(1, 0);
while(q--) {
int a, b; cin >> a >> b;
cout << get_lca(a, b) << nl;
}
}
c, Truy vấn giá trị trên cạnh
Khi mỗi cạnh giữa cha $p$ và con $u$ có một trọng số $w$, ta sẽ dùng một bảng thưa song song với up[u][j] để lưu giá trị tốt nhất khi nhảy $2^j$ bước.
Ta cần thêm một mảng val[limN][limLOG] để lưu giá trị (max/min/gcd/sum/...) trên quãng đường nhảy.
Để tìm max/min/gcd/sum/... từ $u$ đến $v$, ta tìm $L = LCA(u, v)$ và lấy max/min/gcd/sum/... của hai đoạn: $(u \to L)$ và $(v \to L)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
int n;
const int limLOG = 21;
const int limN = 2e5 + 5;
typedef pair<int, int> ii;
vector<ii> adj[limN];
int dist[limN], up[limN][limLOG], mx[limN][limLOG], mn[limN][limLOG];
void dfs(int u, int p, int w) {
up[u][0] = p;
mx[u][0] = w;
mn[u][0] = w;
FOR(j, 1, limLOG) {
up[u][j] = up[up[u][j - 1]][j - 1];
mx[u][j] = max(mx[u][j - 1], mx[up[u][j - 1]][j - 1]);
mn[u][j] = min(mn[u][j - 1], mn[up[u][j - 1]][j - 1]);
}
for(const auto &[v, w]: adj[u]) {
if(v == p) continue;
dist[v] = dist[u] + 1;
dfs(v, u, w);
}
}
int get_kth(int u, int k) {
for(int j = limLOG - 1; j >= 0; j--) {
if(bit(k, j)) {
u = up[u][j];
}
}
return u;
}
int get_lca(int u, int v) {
if(dist[u] < dist[v]) swap(u, v);
u = get_kth(u, dist[u] - dist[v]);
if(u == v) return u;
for(int j = limLOG - 1; j >= 0; j--) {
if(up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
int query_max(int u, int v) {
int lca = get_lca(u, v);
int res = INT_MIN;
auto walk = [&](int node, int k) {
for(int j = limLOG - 1; j >= 0; j--) {
if(bit(k, j)) {
maximize(res, mx[node][j]);
node = up[node][j];
}
}
};
walk(u, dist[u] - dist[lca]); // nhảy từ u lên lca
walk(v, dist[v] - dist[lca]); // nhảy từ v lên lca
return res;
}
int query_min(int u, int v) {
int lca = get_lca(u, v);
int res = INT_MAX;
auto walk = [&](int node, int k) {
for(int j = limLOG - 1; j >= 0; j--) {
if(bit(k, j)) {
minimize(res, mn[node][j]);
node = up[node][j];
}
}
};
walk(u, dist[u] - dist[lca]); // nhảy từ u lên lca
walk(v, dist[v] - dist[lca]); // nhảy từ v lên lca
return res;
}
int main(void) {
cin >> n;
FOR(i, 1, n) {
int u, v, w; cin >> u >> v >> w;
adj[u].eb(v, w);
adj[v].eb(u, w);
}
dfs(1, 0, 0);
int q; cin >> q;
while(q--) {
int a, b; cin >> a >> b;
cout << query_min(a, b) << ' ' << query_max(a, b) << nl;
}
}
5. Euler tour trên cây
Ý tưởng chính của Euler Tour là thực hiện một thuật toán DFS trên cây và duy trì một bộ đếm thời gian toàn cục biến timer. Mỗi khi bước vào một đỉnh hoặc bước ra khỏi một đỉnh, ta ghi lại giá trị timer này.
Dạng 1: Truy vấn / Cập nhật Cây con (Subtree Queries)
Đây là dạng Euler Tour được sử dụng nhiều nhất. Chúng ta chỉ cần lưu lại thời điểm bắt đầu thăm đỉnh $u$ và thời điểm kết thúc thăm toàn bộ cây con gốc $u$.
tin[u](Time In): Thời điểm đỉnh $u$ được gọi DFS tới.tout[u](Time Out): Thời điểm hàm DFS ở đỉnh $u$ kết thúc (đã thăm xong toàn bộ con cháu của $u$).
Tính chất: Toàn bộ các đỉnh nằm trong cây con của $u$ sẽ có tin nằm trong đoạn $[tin[u], tout[u]]$. Điều này có nghĩa là một cây con đã được biến thành một đoạn liên tiếp trên mảng một chiều.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int limN = 2e5 + 5;
vector<int> adj[limN];
int tin[limN], tout[limN];
int timer = 0;
int euler[limN]; // mảng 1 chiều sau khi trải phẳng
void dfs(int u, int p) {
tin[u] = ++timer;
euler[timer] = u; // lưu lại đỉnh ở vị trí timer tương ứng
for(const int &v: adj[u]) {
if(v == p) continue;
dfs(v, u);
}
tout[u] = ++timer; //lấy mốc thời gian lớn nhất của cây con
}
int main(void) {
int n; cin >> n;
FOR(i, 1, n) {
int u, v; cin >> u >> v;
adj[u].eb(v);
adj[v].eb(u);
}
dfs(1, 0);
}
Cách dùng: Nếu bài toán yêu cầu “Cộng thêm $X$ vào tất cả các đỉnh trong cây con của $u$”, ta chỉ cần gọi thao tác Update trên Segment Tree hoặc BIT cho đoạn $[tin[u], tout[u]]$ với giá trị $X$. Độ phức tạp: $O(\log N)$.
1
2
3
4
5
6
7
8
9
10
// thao tác 1: Cộng X vào toàn bộ cây con gốc u
// tương đương update mảng hiệu số (Difference Array)
void update_subtree(int u, int X, int n) {
fenwick_tree.update(tin[u], X, n); // cộng X vào đầu đoạn
fenwick_tree.update(tout[u] + 1, -X, n); // trừ X ở ngay sau cuối đoạn
}
// Thao tác 2: Lấy giá trị hiện tại của đỉnh v
int get_node_value(int v) {
return fenwick_tree.query(tin[v]);
}
Dạng 2: Cập nhật Cạnh / Truy vấn Đường đi (Path Queries)
Dạng này tạo ra một mảng có kích thước $2N$. Mỗi đỉnh xuất hiện đúng 2 lần trong mảng trải phẳng: một lần khi đi vào (+) và một lần khi đi ra (-).
- Khi DFS vào đỉnh $u$, ta thêm giá trị của $u$ vào mảng và lưu
tin[u]. - Khi DFS thoát khỏi $u$, ta thêm giá trị đối (hoặc một thao tác hủy) của $u$ vào mảng và lưu
tout[u].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int n, q;
const int limN = 2e5 + 5;
vector<int> adj[limN];
int tin[limN], tout[limN];
int timer = 0;
void dfs(int u, int p) {
tin[u] = ++timer;
// thêm giá trị của u vào vị trí timer (ví dụ: val[timer] = a[u])
for(const int &v: adj[u]) {
if(v == p) continue;
dfs(v, u);
}
tout[u] = ++timer;
// hủy giá trị của u ở vị trí timer (ví dụ: val[timer] = -a[u])
}
Dạng 3: Bài toán Tìm tổ tiên chung gần nhất (LCA)
Dạng này lưu lại đỉnh mỗi khi ta bước qua nó (kể cả lúc đi xuống và lúc quay lui). Mảng sinh ra sẽ có kích thước $2N - 1$.
- Đỉnh $u$ sẽ xuất hiện trong mảng
eulernhiều lần. - Lưu lại vị trí xuất hiện đầu tiên của $u$ trong mảng, gọi là
first_pos[u].
1
2
3
4
5
6
7
8
9
10
11
12
int euler[2 * MAXN];
int first_pos[MAXN];
int timer = 0;
void dfs(int u, int p) {
first_pos[u] = ++timer;
euler[timer] = u;
for (int v : adj[u]) {
if(v == p) continue;
dfs(v, u);
euler[++timer] = u; // quay lui lại u thì ghi u vào mảng
}
}
Cách dùng: Để tìm LCA của $u$ và $v$, giả sử first_pos[u] < first_pos[v], LCA chính là đỉnh có dist nhỏ nhất trong đoạn từ first_pos[u] đến first_pos[v] trên mảng euler. Bài toán LCA trên cây giờ biến thành bài toán RMQ (Range Minimum Query) trên mảng, có thể giải bằng Sparse Table với độ phức tạp $O(1)$ mỗi truy vấn.
6. Quy hoạch động trên cây (Tree DP)
Tree DP cơ bản (Từ dưới lên)
Trạng thái của đỉnh $u$ được tính dựa trên các đỉnh con $v$ của nó.
Bài toán kinh điển: Tìm kích thước của Tập con độc lập lớn nhất (Maximum Independent Set - MIS). Không có bất kỳ 2 đỉnh nào kề nhau được chọn.
- dp[u][0]: Kết quả tối ưu trong cây con gốc $u$ nếu không chọn đỉnh $u$.
- dp[u][1]: Kết quả tối ưu trong cây con gốc $u$ nếu chọn đỉnh $u$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[MAXN][2];
void dfs_basic_dp(int u, int p) {
dp[u][0] = 0;
dp[u][1] = 1; // Chọn chính u thì ban đầu có kích thước 1
for (int v : adj[u]) {
if (v == p) continue;
dfs_basic_dp(v, u);
// Nếu không chọn u, ta có thể chọn hoặc không chọn v (lấy Max)
dp[u][0] += max(dp[v][0], dp[v][1]);
// Nếu chọn u, ta bắt buộc KHÔNG ĐƯỢC chọn v
dp[u][1] += dp[v][0];
}
}
// Đáp án cho toàn bộ cây là: max(dp[root][0], dp[root][1])
Re-rooting DP (Quy hoạch động thay đỉnh gốc / In-Out DP)
Dạng bài yêu cầu tính toán một giá trị cho mọi đỉnh làm gốc với độ phức tạp $\mathcal{O}(N)$:
- Bước 1: DFS từ dưới lên để tính đáp án cho nhánh con (In-DP).
- Bước 2: DFS từ trên xuống để tính phần đóng góp của nhánh ngoài (Out-DP) và cập nhật đáp án cuối cùng.
Bài toán kinh điển: Tính tổng khoảng cách từ đỉnh $u$ đến tất cả các đỉnh còn lại trong cây, áp dụng cho mọi đỉnh $u$.
Thay vì chạy DFS từ mỗi đỉnh mất $\mathcal{O}(N^2)$, ta sẽ làm trong $\mathcal{O}(N)$ với 2 lần DFS:
DFS 1 (Bottom-up): Tính tổng khoảng cách trong cây con của $u$ (dp_in[u]) và kích thước cây con (sz[u]).
DFS 2 (Top-down): Cập nhật đáp án khi dời gốc từ cha $u$ xuống con $v$. Khi dời gốc xuống $v$, các đỉnh trong cây con của $v$ sẽ gần lại 1 bước (giảm sz[v]), còn các đỉnh ngoài cây con của $v$ sẽ xa ra 1 bước (tăng N - sz[v]).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
long long dp_in[MAXN]; // Tổng khoảng cách tới các đỉnh trong cây con
int sz[MAXN]; // Kích thước cây con
long long ans[MAXN]; // Đáp án cuối cùng cho mỗi đỉnh
int N; // Tổng số đỉnh của cây
// Bước 1: DFS từ dưới lên để tính In-DP
void dfs_in(int u, int p) {
sz[u] = 1;
dp_in[u] = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs_in(v, u);
sz[u] += sz[v];
dp_in[u] += dp_in[v] + sz[v]; // Mỗi đỉnh trong cây con v sẽ cách u thêm 1 cạnh
}
}
// Bước 2: DFS từ trên xuống để tính Out-DP (Re-rooting)
void dfs_out(int u, int p) {
// Với gốc ban đầu (thường là 1), đáp án chính là dp_in
// ans[1] = dp_in[1] đã được gán trước khi gọi dfs_out
for (int v : adj[u]) {
if (v == p) continue;
// Công thức dời gốc từ u xuống v:
// ans[v] = ans[u] - (số đỉnh lại gần 1 bước) + (số đỉnh ra xa 1 bước)
ans[v] = ans[u] - sz[v] + (N - sz[v]);
dfs_out(v, u);
}
}
void solve_rerooting() {
// Giả sử đã đọc cây và N
dfs_in(1, 0);
ans[1] = dp_in[1]; // Đỉnh 1 làm gốc chuẩn
dfs_out(1, 0);
// In ra đáp án
for (int i = 1; i <= N; i++) {
cout << ans[i] << " ";
}
}
7. DSU on Tree (Sack / Small to Large Merging)
Kỹ thuật này (còn gọi là thuật toán Sack) dùng để giải các bài toán truy vấn offline trên cây con (ví dụ: đếm số màu phân biệt trong cây con của đỉnh $u$) với độ phức tạp $O(N \log N)$ thay vì $O(N^2)$.
Ý tưởng cốt lõi: Khi gộp kết quả của các cây con lên đỉnh cha, ta luôn giữ lại mảng đánh dấu của thằng con lớn nhất (heavy child - đỉnh có kích thước cây con lớn nhất) và chỉ tính lại thông tin cho các thằng con nhỏ (light children).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
const int limN = 1e5 + 5;
vector<int> adj[limN];
int dist[limN];
int sz[limN];
int is_big[limN], color[limN];
int cnt[limN]; // Mảng đếm tần số (hoặc cấu trúc dữ liệu lưu trạng thái)
int bigChild[limN]; // Lưu thằng con lớn nhất của mỗi đỉnh
int ans[limN]; // Lưu đáp án cho mỗi đỉnh
// Bước 1: DFS để tính sz và tìm bigChild
void dfs(int u, int p) {
sz[u] = 1;
int max_sub = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
sz[u] += sz[v];
if (sz[v] > max_sub) {
max_sub = sz[v];
bigChild[u] = v;
}
}
}
// Hàm thêm/xóa dữ liệu của cây con gốc u
void add_subtree(int u, int p, int val) {
cnt[color[u]] += val; // Giả sử đỉnh u có màu color[u]
// Cập nhật biến kết quả toàn cục ở đây nếu cần
for (int v : adj[u]) {
if (v != p && !is_big[v]) { // Không tính lại bigChild
add_subtree(v, u, val);
}
}
}
// Bước 2: DFS Sack tính kết quả
// keep = 1 nếu u là bigChild của cha nó (cần giữ lại dữ liệu), ngược lại = 0
void dfs_sack(int u, int p, bool keep) {
// Duyệt qua các con nhỏ (light children) trước
for (int v : adj[u]) {
if (v != p && v != bigChild[u]) {
dfs_sack(v, u, 0);
}
}
// Duyệt thằng con lớn (heavy child) và giữ lại dữ liệu của nó
if (bigChild[u]) {
dfs_sack(bigChild[u], u, 1);
is_big[bigChild[u]] = 1; // Đánh dấu để hàm add_subtree bỏ qua
}
// Thêm bản thân đỉnh u và các con nhỏ vào cấu trúc dữ liệu
add_subtree(u, p, 1);
// Ghi nhận đáp án cho đỉnh u
ans[u] = /* Giá trị hiện tại */;
// Dọn dẹp đánh dấu
if (bigChild[u]) {
is_big[bigChild[u]] = 0;
}
// Nếu u không phải là con lớn của cha nó, xóa toàn bộ dữ liệu vừa thêm
if (!keep) {
add_subtree(u, p, -1);
}
}