Bỏ qua để đến nội dung

Gộp nhỏ vào lớn (small to large)

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

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.

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.

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ểnTập chứa x có ít nhất
chưa lần nào1 phần tử
12 phần tử
24 phần tử
k2k phần tử
import sys
from 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:])

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ó.

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:

  • map mà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).

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ố.

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ậpIn ra
7
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
3 2 2 1 2 1 1

Kiểm tra: nhập

10
1 2 2 3 1 3 3 1 2 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
Xem đáp số

3 3 2 2 1 2 1 1 1 1

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

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ậpIn ra
7
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
0 0 2 1 2 1 1

Kiểm tra: nhập

10
1 2 2 3 1 3 3 1 2 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
Xem đáp số

0 2 0 2 1 1 1 1 1 1

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

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ậpIn ra
7
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
2 5 3 3 5 2 3

Kiểm tra: nhập

10
1 2 2 3 1 3 3 1 2 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
Xem đáp số

3 1 3 4 1 3 3 1 2 3

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

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ậpIn ra
7
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
5 2 0 0 0 0 0

Kiểm tra: nhập

10
1 2 2 3 1 3 3 1 2 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
Xem đáp số

12 1 4 0 0 1 0 0 0 0

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

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ậpIn ra
7
1 2
1 3
2 4
2 5
3 6
5 7
2 1 0 0 0 0 0

Kiểm tra: nhập

10
1 2
1 3
1 4
2 5
2 6
3 7
5 8
5 9
5 10
Xem đáp số

1 2 0 0 1 0 0 0 0 0

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

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ậpIn ra
7 4
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
1 2
2 3
3 3
5 2
3
2
0
1

Kiểm tra: nhập

10 5
1 2 2 3 1 3 3 1 2 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
1 3
3 3
2 1
6 2
9 9
Xem đáp số
4
3
2
1
0

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

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ậpIn ra
7 4
1 3 2 3 1 2 2
1 2
1 3
2 4
2 5
3 6
5 7
7 2 1 0 0 0 0

Kiểm tra: nhập

10 0
1 -1 0 1 -1 0 2 -2 1 -1
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
Xem đáp số

11 2 2 0 0 1 0 0 0 0

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

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ậpIn ra
5 6
1 2 1 3 2
1 1 3
2 1
1 2 5
1 3 5
2 2
2 4
1
2
1

Kiểm tra: nhập

8 8
4 4 1 2 1 3 4 2
1 1 2
2 2
1 3 5
1 2 3
2 5
1 6 7
1 7 8
2 6
Xem đáp số
1
2
3

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

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy