Euler tour trên cây
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…).
Thời điểm vào, thời điểm ra
Phần tiêu đề “Thời điểm vào, thời điểm ra”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| Đỉnh | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| vao | 1 | 2 | 6 | 3 | 4 | 7 | 5 |
| ra | 7 | 5 | 7 | 3 | 5 | 7 | 5 |
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ầnvao, ra, cha, sau = euler_tour(n, ke)for u in range(1, n + 1): print(vao[u], ra[u])#include <iostream>#include <vector>#include <algorithm>using namespace std;
int n;vector<vector<int>> ke;vector<int> vao, ra, cha, sau;
// Duyệt DFS từ gốc; cây con của u là các thời điểm vao[u]..ra[u].void eulerTour(int goc) { vao.assign(n + 1, 0); ra.assign(n + 1, 0); cha.assign(n + 1, 0); sau.assign(n + 1, 0); vector<int> conKeTiep(n + 1, 0), nganXep = {goc}; int dongHo = 1; vao[goc] = 1; while (!nganXep.empty()) { int u = nganXep.back(); if (conKeTiep[u] < (int)ke[u].size()) { int v = ke[u][conKeTiep[u]++]; if (v != cha[u]) { // đi vào đỉnh con v cha[v] = u; sau[v] = sau[u] + 1; vao[v] = ++dongHo; nganXep.push_back(v); } } else { // đã duyệt hết cây con của u ra[u] = dongHo; nganXep.pop_back(); } }}
int main() { cin >> n; ke.assign(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); } for (auto &danhSach : ke) sort(danhSach.begin(), danhSach.end()); eulerTour(1); for (int u = 1; u <= n; u++) cout << vao[u] << ' ' << ra[u] << '\n'; return 0;}Đổ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ây | Trên mảng b |
|---|---|
| tổng giá trị cây con của u | tổng đoạn b[vao[u] .. ra[u]] |
| sửa giá trị đỉnh u | sửa một ô b[vao[u]] |
| cộng v cho mọi đỉnh trong cây con của u | cộng v vào cả đoạn [vao[u], ra[u]] |
| số màu khác nhau trong cây con | số 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.
LCA bằng Euler tour và bảng thưa
Phần tiêu đề “LCA bằng Euler tour và bảng thưa”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í | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Đỉnh | 1 | 2 | 4 | 2 | 5 | 7 | 5 | 2 | 1 | 3 | 6 | 3 | 1 |
| Độ sâu | 0 | 1 | 2 | 1 | 2 | 3 | 2 | 1 | 0 | 1 | 2 | 1 | 0 |
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).
Luyện tập
Phần tiêu đề “Luyện tập”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ố.
Nhóm 1. Thời điểm vào, thời điểm ra
Phần tiêu đề “Nhóm 1. Thời điểm vào, thời điểm ra”Bài 1. Thời điểm vào và ra
Phần tiêu đề “Bài 1. Thời điểm vào và ra”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ập | In ra |
|---|---|
71 21 32 42 53 65 7 | 1 72 56 73 34 57 75 5 |
Kiểm tra: nhập
95 11 33 95 28 52 42 76 9Bài 2. Ai là tổ tiên?
Phần tiêu đề “Bài 2. Ai là tổ tiên?”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ập | In ra |
|---|---|
7 41 21 32 42 53 65 72 77 23 44 4 | YESNONOYES |
Kiểm tra: nhập
8 51 22 33 41 55 65 77 81 85 82 68 53 4Bài 3. Tổng giá trị cây con
Phần tiêu đề “Bài 3. Tổng giá trị 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 ≤ 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ập | In ra |
|---|---|
7 31 2 3 4 5 6 71 21 32 42 53 65 7231 | 18928 |
Kiểm tra: nhập
8 45 -2 7 1 0 3 -4 61 22 33 41 55 65 77 85281Nhóm 2. Cây con thành đoạn
Phần tiêu đề “Nhóm 2. Cây con thành đoạn”Bài 4. Tổng cây con có sửa giá trị
Phần tiêu đề “Bài 4. Tổng cây con có sửa giá trị”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ập | In ra |
|---|---|
5 41 1 1 1 11 21 33 43 52 31 4 102 32 1 | 31214 |
Kiểm tra: nhập
7 64 3 2 1 5 6 71 21 32 42 53 65 72 21 7 02 21 1 -102 12 5Bài 5. Cộng cho cả cây con
Phần tiêu đề “Bài 5. Cộng cho cả 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 ≤ 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ập | In ra |
|---|---|
5 40 0 0 0 01 21 33 43 51 3 51 1 22 42 2 | 72 |
Kiểm tra: nhập
7 61 2 3 4 5 6 71 21 32 42 53 65 71 2 102 71 5 -32 72 32 5Bà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ập | In ra |
|---|---|
7 41 21 32 42 53 65 71 22 22 13 3 | 3210 |
Kiểm tra: nhập
10 51 21 32 42 53 63 74 86 96 101 33 32 36 27 2Bài 7. Số màu khác nhau trong cây con
Phần tiêu đề “Bài 7. Số màu khác nhau 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 ≤ 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ập | In ra |
|---|---|
7 31 2 1 3 2 2 31 21 32 42 53 65 7235 | 222 |
Kiểm tra: nhập
9 51 1 2 3 1 2 4 1 31 21 32 42 53 66 76 85 912369Nhóm 3. Đường đi và LCA
Phần tiêu đề “Nhóm 3. Đường đi và LCA”Bài 8. Tổng trên đường đi từ gốc
Phần tiêu đề “Bài 8. Tổng trên đường đi từ gốc”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ập | In ra |
|---|---|
7 41 2 3 4 5 6 71 21 32 42 53 65 72 71 2 02 72 6 | 151310 |
Kiểm tra: nhập
8 63 1 4 1 5 9 2 61 22 33 41 55 65 77 82 42 81 5 -52 81 1 02 6Bài 9. LCA bằng Euler tour và bảng thưa
Phần tiêu đề “Bài 9. LCA bằng Euler tour và bảng thưa”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ập | In ra |
|---|---|
7 41 21 32 42 53 65 74 77 65 52 7 | 2152 |
Kiểm tra: nhập
10 51 21 32 42 53 63 74 86 96 108 59 109 78 210 1Bà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ập | In ra |
|---|---|
7 31 2 3 4 5 6 71 21 32 42 53 65 72 4 71 2 102 4 6 | 1824 |
Kiểm tra: nhập
8 53 1 4 1 5 9 2 61 22 33 41 55 65 77 82 4 82 6 81 5 02 6 82 3 3Bà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ập | In ra |
|---|---|
5 41 1 1 1 11 21 33 43 51 3 22 32 12 4 | 9113 |
Kiểm tra: nhập
7 61 2 3 4 5 6 71 21 32 42 53 65 71 2 12 11 5 -22 21 1 32 3