Gộp nhỏ vào lớn (small to large)
Cây có n đỉnh, mỗi đỉnh có một màu. Với mọi đỉnh u, hỏi cây con của u có bao nhiêu màu khác nhau. Cách tự nhiên là đi từ lá lên gốc (quy hoạch động trên cây): tập màu của u là hợp các tập màu của các con, thêm màu của u.
Vấn đề là chép tập. Nếu cây là một đường thẳng 1 - 2 - 3 - … - n, tập của đỉnh n có 1 màu, đỉnh n - 1 phải chép lại 1 màu rồi thêm 1, đỉnh n - 2 chép lại 2 màu… Tổng cộng 1 + 2 + … + n, khoảng n2/2 lần chép.
Ý tưởng: giữ lại tập lớn nhất
Phần tiêu đề “Ý tưởng: giữ lại tập lớn nhất”Không chép tập lớn nhất. Đỉnh u lấy luôn tập của đứa con có tập lớn nhất làm tập của mình (không tốn bước nào, chỉ đổi tên), rồi đổ từng phần tử của các tập nhỏ hơn vào đó, cuối cùng thêm màu của u.
Với đường thẳng ở trên, mỗi đỉnh chỉ có một con nên lấy luôn tập của con, chỉ thêm 1 màu: tổng cộng n bước.
Vì sao chỉ khoảng n log n bước?
Phần tiêu đề “Vì sao chỉ khoảng n log n bước?”Theo dõi một phần tử x. Mỗi lần x bị đổ từ tập A sang tập B thì A nhỏ hơn hoặc bằng B, nên tập mới chứa x có ít nhất 2 lần số phần tử của A. Nói cách khác: mỗi lần x bị chuyển, tập chứa x lớn gấp đôi trở lên.
Tập không thể có quá n phần tử, mà gấp đôi từ 1 lên n chỉ được khoảng log2n lần. Vậy mỗi phần tử bị chuyển không quá log2n lần, cả cây không quá n log2n lần chuyển. Với n = 2 × 105 là khoảng 3,6 × 106 lần, so với khoảng 2 × 1010 lần chép nếu luôn chép mọi tập.
| Lần bị chuyển | Tập chứa x có ít nhất |
|---|---|
| chưa lần nào | 1 phần tử |
| 1 | 2 phần tử |
| 2 | 4 phần tử |
| k | 2k phần tử |
import sysfrom collections import deque
def thu_tu_bfs(n, ke, goc=1): """Thứ tự BFS từ gốc (cha đứng trước con) và cha của từng đỉnh.""" cha = [0] * (n + 1) thu_tu = [goc] da_tham = [False] * (n + 1) da_tham[goc] = True for u in thu_tu: for v in ke[u]: if not da_tham[v]: da_tham[v] = True cha[v] = u thu_tu.append(v) return thu_tu, cha
def so_mau_cay_con(n, ke, mau): """Số màu khác nhau trong cây con của mọi đỉnh.""" thu_tu, cha = thu_tu_bfs(n, ke) tap = [None] * (n + 1) ket_qua = [0] * (n + 1) for u in reversed(thu_tu): # con được xử lý trước cha con = [v for v in ke[u] if v != cha[u]] if con: lon_nhat = max(con, key=lambda v: len(tap[v])) tap_u = tap[lon_nhat] # lấy luôn tập lớn nhất, không chép for v in con: if v != lon_nhat: tap_u.update(tap[v]) # đổ tập nhỏ vào tập lớn tap[v] = None else: tap_u = set() tap_u.add(mau[u]) tap[u] = tap_u ket_qua[u] = len(tap_u) return ket_qua
du_lieu = sys.stdin.buffer.read().split()n = int(du_lieu[0])mau = [0] + [int(x) for x in du_lieu[1:1 + n]]ke = [[] for _ in range(n + 1)]for i in range(n - 1): u, v = int(du_lieu[1 + n + 2 * i]), int(du_lieu[2 + n + 2 * i]) ke[u].append(v) ke[v].append(u)print(*so_mau_cay_con(n, ke, mau)[1:])#include <iostream>#include <vector>#include <set>using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> mau(n + 1); for (int u = 1; u <= n; u++) cin >> mau[u]; 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); } // thứ tự BFS: cha đứng trước con vector<int> thuTu = {1}, cha(n + 1, 0); for (size_t k = 0; k < thuTu.size(); k++) for (int v : ke[thuTu[k]]) if (v != cha[thuTu[k]]) { cha[v] = thuTu[k]; thuTu.push_back(v); } vector<set<int>> tap(n + 1); vector<int> ketQua(n + 1); for (int k = n - 1; k >= 0; k--) { // con được xử lý trước cha int u = thuTu[k]; for (int v : ke[u]) { if (v == cha[u]) continue; if (tap[v].size() > tap[u].size()) swap(tap[u], tap[v]); // đổi tên, không chép for (int x : tap[v]) tap[u].insert(x); // đổ tập nhỏ vào tập lớn set<int>().swap(tap[v]); // giải phóng tập nhỏ } tap[u].insert(mau[u]); ketQua[u] = tap[u].size(); } for (int u = 1; u <= n; u++) cout << ketQua[u] << (u < n ? ' ' : '\n'); return 0;}Trong C++, swap hai set chỉ đổi phần quản lý bên trong, không chép phần tử nào. Đổi tập của u với tập của con mỗi khi
con có tập lớn hơn thì cuối cùng tập của u là tập lớn nhất, các tập còn lại đều được đổ vào nó.
Không chỉ là tập màu
Phần tiêu đề “Không chỉ là tập màu”Kỹ thuật dùng được cho mọi thông tin dạng “tập các phần tử” mà thêm một phần tử thì cập nhật nhanh:
mapmàu → số lần xuất hiện, kèm màu xuất hiện nhiều nhất (bài 3);mapđộ sâu → số đỉnh ở độ sâu đó (bài 5);- khi đổ tập nhỏ vào tập lớn, đếm trước rồi mới gộp các cặp phần tử, một phần tử ở tập nhỏ, một ở tập lớn (bài 7).
Nó cũng không chỉ dùng trên cây: khi DSU gộp hai nhóm, mỗi nhóm giữ một tập, luôn đổ tập nhỏ vào tập lớn thì tổng số lần chuyển cũng chỉ khoảng n log n (bài 8).
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 8 bài, chia thành 3 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. Gộp tập màu
Phần tiêu đề “Nhóm 1. Gộp tập màu”Bài 1. Số màu khác nhau trong mọi cây con
Phần tiêu đề “Bài 1. Số màu khác nhau trong mọi cây con”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có màu cu. Dòng đầu có n (1 ≤ n ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ 109), n - 1 dòng sau là các cạnh. In ra n số, số thứ u là số màu khác nhau trong cây con của u.
Ví dụ:
| Nhập | In ra |
|---|---|
71 2 1 3 2 2 31 21 32 42 53 65 7 | 3 2 2 1 2 1 1 |
Kiểm tra: nhập
101 2 2 3 1 3 3 1 2 31 21 32 42 53 63 74 86 96 10Bài 2. Màu chỉ xuất hiện một lần
Phần tiêu đề “Bài 2. Màu chỉ xuất hiện một lần”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có màu cu. Dòng đầu có n (1 ≤ n ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ 109), n - 1 dòng sau là các cạnh. In ra n số, số thứ u là số màu xuất hiện đúng một lần trong cây con của u.
Ví dụ:
| Nhập | In ra |
|---|---|
71 2 1 3 2 2 31 21 32 42 53 65 7 | 0 0 2 1 2 1 1 |
Kiểm tra: nhập
101 2 2 3 1 3 3 1 2 31 21 32 42 53 63 74 86 96 10Bài 3. Màu áp đảo
Phần tiêu đề “Bài 3. Màu áp đảo”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có màu cu. Dòng đầu có n (1 ≤ n ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ n), n - 1 dòng sau là các cạnh. Trong cây con của u, màu áp đảo là màu có số lần xuất hiện nhiều nhất (có thể có nhiều màu cùng nhiều nhất). In ra n số, số thứ u là tổng các màu áp đảo trong cây con của u.
Ví dụ:
| Nhập | In ra |
|---|---|
71 2 1 3 2 2 31 21 32 42 53 65 7 | 2 5 3 3 5 2 3 |
Kiểm tra: nhập
101 2 2 3 1 3 3 1 2 31 21 32 42 53 63 74 86 96 10Bài 4. Số cặp đỉnh cùng màu
Phần tiêu đề “Bài 4. Số cặp đỉnh cùng màu”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có màu cu. Dòng đầu có n (1 ≤ n ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ 109), n - 1 dòng sau là các cạnh. In ra n số, số thứ u là số cặp đỉnh khác nhau (không tính thứ tự) trong cây con của u có cùng màu.
Ví dụ:
| Nhập | In ra |
|---|---|
71 2 1 3 2 2 31 21 32 42 53 65 7 | 5 2 0 0 0 0 0 |
Kiểm tra: nhập
101 2 2 3 1 3 3 1 2 31 21 32 42 53 63 74 86 96 10Nhóm 2. Gộp theo độ sâu, đếm cặp
Phần tiêu đề “Nhóm 2. Gộp theo độ sâu, đếm cặp”Bài 5. Độ sâu đông đỉnh nhất
Phần tiêu đề “Bài 5. Độ sâu đông đỉnh nhất”Cây có n đỉnh, gốc là đỉnh 1. Dòng đầu có n (1 ≤ n ≤ 2 × 105), n - 1 dòng sau là các cạnh. Với mỗi đỉnh u, xét các đỉnh trong cây con của u theo khoảng cách tới u (u cách chính nó 0). In ra n số, số thứ u là khoảng cách k nhỏ nhất mà số đỉnh trong cây con của u cách u đúng k là nhiều nhất.
Ví dụ:
| Nhập | In ra |
|---|---|
71 21 32 42 53 65 7 | 2 1 0 0 0 0 0 |
Kiểm tra: nhập
101 21 31 42 52 63 75 85 95 10Bài 6. Bao nhiêu đỉnh màu c trong cây con
Phần tiêu đề “Bài 6. Bao nhiêu đỉnh màu c trong cây con”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có màu cu. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ 109), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, c. Với mỗi câu hỏi, in ra số đỉnh màu c trong cây con của u.
Ví dụ:
| Nhập | In ra |
|---|---|
7 41 2 1 3 2 2 31 21 32 42 53 65 71 22 33 35 2 | 3201 |
Kiểm tra: nhập
10 51 2 2 3 1 3 3 1 2 31 21 32 42 53 63 74 86 96 101 33 32 16 29 9Bài 7. Cặp đỉnh có tổng bằng K
Phần tiêu đề “Bài 7. Cặp đỉnh có tổng bằng K”Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có giá trị au. Dòng đầu có n, K (1 ≤ n ≤ 2 × 105, |K| ≤ 2 × 109), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. In ra n số, số thứ u là số cặp đỉnh khác nhau (không tính thứ tự) x, y trong cây con của u mà ax + ay = K.
Ví dụ:
| Nhập | In ra |
|---|---|
7 41 3 2 3 1 2 21 21 32 42 53 65 7 | 7 2 1 0 0 0 0 |
Kiểm tra: nhập
10 01 -1 0 1 -1 0 2 -2 1 -11 21 32 42 53 63 74 86 96 10Nhóm 3. Gộp nhóm trong DSU
Phần tiêu đề “Nhóm 3. Gộp nhóm trong DSU”Bài 8. Gộp nhóm, đếm màu trong nhóm
Phần tiêu đề “Bài 8. Gộp nhóm, đếm màu trong nhóm”Có n người, người i mang áo màu ci, ban đầu mỗi người là một nhóm. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có c1, …, cn (1 ≤ ci ≤ 109). q dòng sau mỗi dòng là 1 x y (gộp nhóm của x và nhóm của y, nếu đã cùng nhóm thì thôi) hoặc 2 x (hỏi trong nhóm của x có bao nhiêu màu áo khác nhau). In ra đáp số các câu hỏi loại 2.
Ví dụ:
| Nhập | In ra |
|---|---|
5 61 2 1 3 21 1 32 11 2 51 3 52 22 4 | 121 |
Kiểm tra: nhập
8 84 4 1 2 1 3 4 21 1 22 21 3 51 2 32 51 6 71 7 82 6