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

Euler tour trên cây

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

Nhiều bài trên cây hỏi về cây con: tổng giá trị các đỉnh trong cây con của u, cộng thêm v cho mọi đỉnh trong cây con, có bao nhiêu màu khác nhau trong cây con. Duyệt cả cây con mỗi câu hỏi mất tới n bước. Euler tour đánh số lại các đỉnh để mỗi cây con thành một đoạn liên tiếp, rồi dùng các cấu trúc trên mảng đã học (tổng tiền tố, cây Fenwick, cây phân đoạn…).

Chạy DFS từ gốc, giữ một đồng hồ đếm. Mỗi lần đi vào một đỉnh mới, tăng đồng hồ lên 1 và ghi lại: đó là vao[u]. Khi duyệt xong mọi đỉnh trong cây con của u và rời khỏi u, ghi lại giá trị đồng hồ lúc đó: ra[u].

Cây 7 đỉnh, gốc 1, cạnh 1-2, 1-3, 2-4, 2-5, 3-6, 5-7, duyệt các con theo số tăng dần:

1
/ \
2 3
/ \ \
4 5 6
|
7
Đỉnh1234567
vao1263475
ra7573575

Xếp các đỉnh theo vao được dãy 1 2 4 5 7 3 6. Cây con của 2 gồm 2, 4, 5, 7, đúng là các vị trí 2 đến 5 của dãy.

Vì sao cây con là một đoạn liên tiếp? DFS đi vào u rồi duyệt hết cây con của u trước khi rời u. Trong khoảng thời gian đó nó không đi ra ngoài cây con, nên các đỉnh được đánh số liên tiếp từ vao[u] đến ra[u], không lẫn đỉnh nào khác. Cây con của u có đúng ra[u] - vao[u] + 1 đỉnh.

Kiểm tra tổ tiên: u là tổ tiên của v (hoặc u = v) khi và chỉ khi v nằm trong cây con của u, tức là vao[u] ≤ vao[v] ≤ ra[u]. Một phép so sánh, không cần đi lên từng bước.

Cây có thể sâu tới n tầng, đệ quy trong Python dễ bị tràn. Chương trình dưới dùng ngăn xếp tự quản lý.

import sys
def euler_tour(n, ke, goc=1):
"""Duyệt DFS từ gốc. Trả về vao, ra, cha, sau (độ sâu), đánh số từ 1;
cây con của u là các thời điểm vao[u]..ra[u]."""
vao, ra = [0] * (n + 1), [0] * (n + 1)
cha, sau = [0] * (n + 1), [0] * (n + 1)
con_ke_tiep = [0] * (n + 1) # đỉnh u đã xét tới con thứ mấy
dong_ho = 1
vao[goc] = 1
ngan_xep = [goc]
while ngan_xep:
u = ngan_xep[-1]
if con_ke_tiep[u] < len(ke[u]):
v = ke[u][con_ke_tiep[u]]
con_ke_tiep[u] += 1
if v != cha[u]: # đi vào đỉnh con v
cha[v], sau[v] = u, sau[u] + 1
dong_ho += 1
vao[v] = dong_ho
ngan_xep.append(v)
else: # đã duyệt hết cây con của u
ra[u] = dong_ho
ngan_xep.pop()
return vao, ra, cha, sau
n = int(sys.stdin.readline())
ke = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, sys.stdin.readline().split())
ke[u].append(v)
ke[v].append(u)
for danh_sach in ke:
danh_sach.sort() # duyệt các con theo số tăng dần
vao, ra, cha, sau = euler_tour(n, ke)
for u in range(1, n + 1):
print(vao[u], ra[u])

Đổi câu hỏi trên cây thành câu hỏi trên mảng

Phần tiêu đề “Đổi câu hỏi trên cây thành câu hỏi trên mảng”

Đặt giá trị của đỉnh u vào ô vao[u] của một mảng b. Khi đó:

Trên câyTrên mảng b
tổng giá trị cây con của utổng đoạn b[vao[u] .. ra[u]]
sửa giá trị đỉnh usửa một ô b[vao[u]]
cộng v cho mọi đỉnh trong cây con của ucộng v vào cả đoạn [vao[u], ra[u]]
số màu khác nhau trong cây consố giá trị khác nhau trên đoạn (dùng thuật toán Mo)

Đường đi từ gốc cũng làm được, theo chiều ngược lại: muốn tính tổng giá trị trên đường từ gốc tới v, để ý giá trị của đỉnh u góp vào tổng của mọi đỉnh trong cây con của u. Vậy cộng giá trị của u vào cả đoạn [vao[u], ra[u]] (trên mảng hiệu: cộng tại vao[u], trừ tại ra[u] + 1). Tổng trên đường từ gốc tới v là tổng tiền tố đến vao[v]. Với cây Fenwick, sửa giá trị một đỉnh và hỏi tổng đường đi từ gốc đều mất khoảng log n bước.

Ví dụ với cây trên: giá trị của đỉnh 2 được cộng vào các ô 2 đến 5 (đỉnh 2, 4, 5, 7). Tổng tiền tố đến vao[7] = 5 gồm phần của đỉnh 1 (ô 1 đến 7), đỉnh 2 (ô 2 đến 5), đỉnh 5 (ô 4 đến 5), đỉnh 7 (ô 5): đúng các đỉnh trên đường 1 → 2 → 5 → 7.

Ghi lại đỉnh mỗi lần đi qua, cả lúc đi xuống lẫn lúc quay về từ một con. Cây trên cho dãy 2n - 1 = 13 đỉnh:

Vị trí12345678910111213
Đỉnh1242575213631
Độ sâu0121232101210

Gọi dau[u] là vị trí đầu tiên u xuất hiện. Đi từ u tới v trong dãy (từ vị trí dau[u] tới dau[v]), DFS phải đi lên tới tổ tiên chung gần nhất rồi mới đi xuống v, và không lên cao hơn nó. Nên LCA của u và v là đỉnh có độ sâu nhỏ nhất trong đoạn đó.

Ví dụ LCA(4, 7): dau[4] = 3, dau[7] = 6, đoạn 3..6 là 4 2 5 7, đỉnh nông nhất là 2.

Tìm nhỏ nhất trên đoạn của một dãy không đổi là việc của bảng thưa: chuẩn bị khoảng 2n log n bước, sau đó mỗi câu hỏi LCA chỉ một phép so sánh (so với log n bước của nhảy nhị phân).

Gồm 11 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. Dòng đầu có n (1 ≤ n ≤ 2 × 105), n - 1 dòng sau mỗi dòng là một cạnh u v. Chạy DFS từ gốc, ở mỗi đỉnh duyệt các con theo số tăng dần, đồng hồ tăng 1 mỗi khi đi vào một đỉnh mới (đỉnh 1 có thời điểm vào là 1). In ra n dòng, dòng thứ u có vao[u] và ra[u] (giá trị đồng hồ khi rời u).

Ví dụ:

NhậpIn ra
7
1 2
1 3
2 4
2 5
3 6
5 7
1 7
2 5
6 7
3 3
4 5
7 7
5 5

Kiểm tra: nhập

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

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, q (1 ≤ n, q ≤ 2 × 105), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v. Với mỗi câu hỏi, in YES nếu u là tổ tiên của v (mọi đỉnh coi là tổ tiên của chính nó), ngược lại in NO.

Ví dụ:

NhậpIn ra
7 4
1 2
1 3
2 4
2 5
3 6
5 7
2 7
7 2
3 4
4 4
YES
NO
NO
YES

Kiểm tra: nhập

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

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, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có một đỉnh u. Với mỗi câu hỏi, in ra tổng giá trị các đỉnh trong cây con của u.

Ví dụ:

NhậpIn ra
7 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
5 7
2
3
1
18
9
28

Kiểm tra: nhập

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

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, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. q dòng sau mỗi dòng là 1 u x (gán au = x) hoặc 2 u (hỏi tổng giá trị cây con của u). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
5 4
1 1 1 1 1
1 2
1 3
3 4
3 5
2 3
1 4 10
2 3
2 1
3
12
14

Kiểm tra: nhập

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

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, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. q dòng sau mỗi dòng là 1 u x (cộng x vào giá trị mọi đỉnh trong cây con của u, |x| ≤ 104) hoặc 2 u (hỏi giá trị hiện tại của đỉnh u). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
5 4
0 0 0 0 0
1 2
1 3
3 4
3 5
1 3 5
1 1 2
2 4
2 2
7
2

Kiểm tra: nhập

7 6
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
5 7
1 2 10
2 7
1 5 -3
2 7
2 3
2 5
Xem đáp số
17
14
3
12

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

Bài 6. Đếm đỉnh ở độ sâu d trong cây con

Phần tiêu đề “Bài 6. Đếm đỉnh ở độ sâu d trong cây con”

Cây có n đỉnh, gốc là đỉnh 1 có độ sâu 0, con của đỉnh độ sâu h có độ sâu h + 1. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 105), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, d (0 ≤ d ≤ n). Với mỗi câu hỏi, in ra số đỉnh trong cây con của u có độ sâu đúng bằng d.

Ví dụ:

NhậpIn ra
7 4
1 2
1 3
2 4
2 5
3 6
5 7
1 2
2 2
2 1
3 3
3
2
1
0

Kiểm tra: nhập

10 5
1 2
1 3
2 4
2 5
3 6
3 7
4 8
6 9
6 10
1 3
3 3
2 3
6 2
7 2
Xem đáp số
3
2
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, q (1 ≤ n, q ≤ 105), dòng thứ hai có c1, …, cn (1 ≤ cu ≤ n), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có một đỉnh u. Với mỗi câu hỏi, in ra số màu khác nhau trong cây con của u.

Ví dụ:

NhậpIn ra
7 3
1 2 1 3 2 2 3
1 2
1 3
2 4
2 5
3 6
5 7
2
3
5
2
2
2

Kiểm tra: nhập

9 5
1 1 2 3 1 2 4 1 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
5 9
1
2
3
6
9
Xem đáp số
4
2
3
3
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ó giá trị au. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. q dòng sau mỗi dòng là 1 u x (gán au = x) hoặc 2 v (hỏi tổng giá trị các đỉnh trên đường đi từ gốc tới v, tính cả hai đầu). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
7 4
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
5 7
2 7
1 2 0
2 7
2 6
15
13
10

Kiểm tra: nhập

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

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, q (1 ≤ n ≤ 2 × 105, 1 ≤ q ≤ 5 × 105), n - 1 dòng sau là các cạnh, q dòng sau mỗi dòng có u, v. Với mỗi câu hỏi, in ra tổ tiên chung gần nhất của u và v.

Ví dụ:

NhậpIn ra
7 4
1 2
1 3
2 4
2 5
3 6
5 7
4 7
7 6
5 5
2 7
2
1
5
2

Kiểm tra: nhập

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

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

Bài 10. Tổng trên đường đi giữa hai đỉnh

Phần tiêu đề “Bài 10. Tổng trên đường đi giữa hai đỉnh”

Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có giá trị au. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. q dòng sau mỗi dòng là 1 u x (gán au = x) hoặc 2 u v (hỏi tổng giá trị các đỉnh trên đường đi từ u tới v, tính cả hai đầu). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
7 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
5 7
2 4 7
1 2 10
2 4 6
18
24

Kiểm tra: nhập

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

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

Bài 11. Cộng cho cây con, hỏi tổng cây con

Phần tiêu đề “Bài 11. Cộng cho cây con, hỏi tổng cây con”

Cây có n đỉnh, gốc là đỉnh 1, đỉnh u có giá trị au. Dòng đầu có n, q (1 ≤ n, q ≤ 105), dòng thứ hai có a1, …, an (|au| ≤ 109), n - 1 dòng sau là các cạnh. q dòng sau mỗi dòng là 1 u x (cộng x vào giá trị mọi đỉnh trong cây con của u, |x| ≤ 104) hoặc 2 u (hỏi tổng giá trị cây con của u). In ra đáp số các câu hỏi loại 2.

Ví dụ:

NhậpIn ra
5 4
1 1 1 1 1
1 2
1 3
3 4
3 5
1 3 2
2 3
2 1
2 4
9
11
3

Kiểm tra: nhập

7 6
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
5 7
1 2 1
2 1
1 5 -2
2 2
1 1 3
2 3
Xem đáp số
32
18
15

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