¶ Đường đi Euler trên cây
Người viết:
- Cao Thanh Hậu - Đại học Khoa học Tự nhiên - ĐHQG-HCM
Reviewer:
- Lê Minh Hoàng - Đại học Khoa học Tự nhiên - ĐHQG-HCM
- Trịnh Quang Anh - University of Melbourne
- Nguyễn Anh Bảo - Đại học Bách Khoa Hà Nội
- Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên - ĐHQG-HCM
- Hoàng Xuân Nhật - Đại học Khoa học Tự nhiên - ĐHQG-HCM
- Ngô Nhật Quang - Trường THPT chuyên Khoa học Tự Nhiên - ĐHQGHN
¶ Giới thiệu
Đường đi Euler trên cây (Euler tour on tree) là một phương pháp hữu dụng được dùng nhiều trong các bài toán trên cây. Đây có thể được hiểu là một cách trải phẳng cây, từ đó các thao tác với cây có thể chuyển về thao tác với dãy một chiều.
¶ Bài toán
Trước khi tìm hiểu sâu hơn về đường đi Euler trên cây, mời bạn đọc xem qua bài toán sau đây.
¶ Truy vấn trên cây
Cho một cây có đỉnh đánh số từ đến , đỉnh là đỉnh gốc của cây. Ban đầu, mỗi đỉnh của cây có giá trị .
Thực hiện các truy vấn thuộc một trong hai loại sau:
- : Thay đổi giá trị đỉnh thành .
- : Tính tổng giá trị các đỉnh thuộc cây con gốc (*).
Giới hạn: .
Hình
(*): Cây con gốc là cây tạo bởi tất cả những đỉnh mà đường đi từ đỉnh đó đến đỉnh gốc của cây có chứa , và tất cả những cạnh nối 2 đỉnh mà đường đi từ đỉnh đó đến đỉnh gốc có chứa đỉnh . Ví dụ, cây trong hình có gốc cây là đỉnh , với thì cây con gốc bao gồm các phần màu xanh lá (cả cạnh và đỉnh).
¶ Thuật toán ngây thơ
Ý tưởng khá đơn giản: duyệt qua tất cả các đỉnh con để tìm đáp án cho truy vấn loại .
const int N = 100000 + 5;
int val[N]; // val[u] là giá trị đỉnh u
int parent[N]; // parent[u] là đỉnh cha của đỉnh u
vector<int> adj[N]; // adj[u] là danh sách các đỉnh kề với đỉnh u
void change(int u, int x) { // thay đổi giá trị đỉnh u
val[u] = x;
}
long long sum(int u) { // tổng các giá trị của cây con gốc u
long long s = val[u];
for (int v : adj[u]) {
if (v != parent[u]) {
s += sum(v);
}
}
return s;
}
Độ phức tạp của thuật toán:
- Với các truy vấn loại , ta chỉ thay đổi giá trị của đỉnh nên độ phức tạp cho truy vấn này là .
- Với các truy vấn loại , ta cần duyệt qua tất cả các đỉnh thuộc cây con gốc , trong trường hợp tệ nhất, độ phức tạp cho mỗi truy vấn như thế lên đến .
Vậy thuật toán có độ phức tạp , quá lớn để giải được bài toán này.
Phần sau đây sẽ giới thiệu về một phương pháp rất đặc biệt, có thể được dùng để giải quyết bài toán "hóc búa" trên.
¶ Đường đi Euler trên cây
¶ Định nghĩa
Từ đồ thị cây tạo đồ thị có hướng theo cách sau: với mỗi cạnh , thêm vào hai cạnh có hướng và .
Thể hiện chu trình Euler (**) trên đồ thị bằng một dãy các đỉnh, dãy đỉnh này cũng biểu diễn đường đi Euler trên cây .
(**): Chu trình Euler của một đồ thị là một đường đi trên đồ thị đó, trong đó đỉnh bắt đầu trùng với đỉnh kết thúc của đường đi, và mỗi cạnh của đồ thị được đường đi thăm qua đúng một lần.
Hình
Với đồ thị cây hình , đường đi Euler biểu diễn bằng dãy các đỉnh: 1 2 3 2 4 2 1 5 1, cũng là dãy các đỉnh biểu diễn chu trình Euler trên đồ thị hình .
¶ Sự tồn tại của đường đi Euler
Có thể chứng minh rằng, chu trình Euler luôn tồn tại trong đồ thị , hay là đồ thị Euler.
¶ Định lý
Một đồ thị có hướng là đồ thị Euler nếu và chỉ nếu:
- Với mọi đỉnh thuộc đồ thị, bậc vào của bằng bậc ra của .
- Mọi đỉnh có bậc khác thuộc cùng thành phần liên thông.
¶ Chứng minh
Dễ thấy, là đồ thị liên thông vì được xây dựng từ một cây.
Mỗi khi xây dựng cạnh có hướng và trong , bậc vào của đỉnh và tăng lên , bậc ra của và cũng tăng . Vì vậy với mọi đỉnh trong đồ thị , bậc vào của luôn bằng bậc ra của .
Từ và có thể khẳng định, là đồ thị Euler.
¶ Cài đặt
Tham khảo đoạn code c++ dưới đây:
#include<bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
int n, m = 0, root = 1;
int h[N], st[N], en[N], tour[N];
vector<int> adj[N];
// Trong các giá trị bên trên:
// h[u] là khoảng cách từ đỉnh gốc đến đỉnh u.
// st[u] là vị trí đầu tiên của đỉnh u trong mảng tour.
// en[u] là vị trí cuối cùng của đỉnh u trong mảng tour.
void input() {
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void add(int u) {
tour[++m] = u;
en[u] = m;
}
void dfs(int u, int parent_of_u) {
h[u] = h[parent_of_u] + 1;
add(u);
st[u] = m;
for (int v : adj[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
if (u != root) add(parent_of_u);
}
int main() {
input();
dfs(root, 0);
return 0;
}
Mỗi khi truy cập một đỉnh bất kỳ, ta thêm đỉnh đó vào đường đi. Trước khi rời khỏi một đỉnh (trở về cha), nếu đỉnh đó khác gốc của cây, ta thêm cha của đỉnh vào đường đi.
Áp dụng code trên vào đồ thị hình , mảng cuối cùng chứa các giá trị: 1 2 3 2 4 2 1 5 1, đây chính là đường đi Euler theo định nghĩa ban đầu.
¶ Tính chất
Như đã giới thiệu, ứng dụng chính của Euler tour là trải phẳng cây, từ đó bài toán trên cây chuyển về bài toán với dãy số. Vậy cụ thể mối liên hệ giữa cây với dãy số là như thế nào, mời bạn đọc cùng tìm hiểu.
¶ Các mối quan hệ về vị trí
¶ Cơ sở
Sau đây là một số tính chất cơ bản nhất của đường đi Euler.
Đỉnh thuộc cây con gốc nếu và chỉ nếu .
Đỉnh không thuộc cây con gốc và không thuộc cây con gốc , hay và không có quan hệ tổ tiên nếu và chỉ nếu hai đoạn và không giao nhau, nghĩa là hoặc .
Từ hai tính chất trên ta nhận xét được rằng, với hai đỉnh , bất kì, hai đoạn và hoặc là không giao nhau, hoặc một đoạn hoàn toàn bao đoạn còn lại.
Hình
¶ Giải thích
Từ khi thăm đỉnh lần đầu tiên đến khi thăm đỉnh lần cuối cùng, đường đi Euler đi qua và chỉ đi qua các đỉnh thuộc cây con gốc . Vậy với mọi đỉnh thuộc cây con gốc , mọi vị trí của đều thuộc đoạn (tính chất thứ nhất).
Với hai đỉnh và không có quan hệ tổ tiên thì đỉnh được thăm lần cuối cùng trước khi đỉnh được thăm lần đầu tiên (hoặc ngược lại, đỉnh được thăm lần cuối cùng trước khi đỉnh được thăm lần đầu tiên). Vậy trong trường hợp này hoặc (tính chất thứ hai).
¶ Ứng dụng
¶ Cập nhật, truy vấn đối với đỉnh và cây con
Đây là ứng dụng phổ biến nhất của đường đi Euler trên cây.
Ở ứng dụng này, ta cần thay đổi đường đi Euler một chút.
Gọi là dãy biểu diễn đường đi Euler. Với mỗi đỉnh , xóa tất cả các giá trị xuất hiện trong ngoại trừ giá trị đầu tiên.
Ví dụ, có dãy ban đầu gồm các giá trị:
1 2 3 2 4 2 1 5 1
=> 1 2 3 (2) 4 (2) (1) 5 (1)
Các phần tử trong ngoặc là các phần tử cần xóa, sau khi xóa, dãy còn lại:
1 2 3 4 5
Ta cũng có thể tìm trực tiếp dãy (thay vì thay đổi từ dãy đường đi Euler ban đầu) như sau:
void dfs(int u, int parent_of_u) {
tour[++m] = u;
st[u] = m;
for (int v : adj[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
en[u] = m;
}
Trong đó, là vị trí cuối cùng nhất của một đỉnh thuộc cây con gốc .
¶ Cơ sở
Trong dãy , tất cả các đỉnh thuộc cây con gốc nằm liên tiếp từ vị trí đến vị trí . Tất cả các đỉnh có vị trí thuộc đoạn đều thuộc cây con gốc .
Lưu ý rằng sau khi thay đổi như trên, mỗi đỉnh chỉ xuất hiện trong đúng lần, và ý nghĩa mảng cũng đã được thay đổi.
¶ Giải thích
Đây thực chất là một cách phát biểu khác của tính chất đầu tiên được nêu ở phần trước: Đỉnh thuộc cây con gốc nếu và chỉ nếu .
Và nhận xét rằng tính chất này giữ nguyên tính đúng đắn với dãy đã thay đổi.
Vậy về cơ bản, mục đích của việc biến đổi dãy nêu trên là để mỗi đỉnh chỉ xuất hiện đúng lần, sẽ tiện hơn trong xử lý.
¶ Thuật toán
Từ tính chất đó, dễ thấy rằng các thao tác với cây con có thể chuyển thành thao tác với đoạn.
Cụ thể, thao tác cập nhật hoặc truy vấn đối với cây con gốc có thể chuyển thành thao tác tương ứng đối với đoạn .
Ví dụ:
Trong đoạn code dưới đây, hàm cho phép tăng giá trị của đỉnh thêm đơn vị. Hàm cho phép tính tổng giá trị các đỉnh thuộc cây con gốc (sử dụng kiểu dữ liệu Fenwick Tree - cây BIT).
const int N = 100000 + 5;
int bit[N]; // cây BIT
int st[N], en[N]; // các mảng lưu vị trí đầu tiên / sau cùng của đỉnh, lưu ý rằng mảng en đã có sự thay đổi ý nghĩa
// BIT
void add(int i, int x) {
for (; i <= n; i += i & (-i)) bit[i] += x;
}
long long sumPrefix(int i) {
long long ans = 0;
for (; i > 0; i &= (i - 1)) ans += bit[i];
return ans;
}
// Truy vấn
void change(int u, int v) {
// thay đổi giá trị đỉnh u
add(st[u], x);
}
long long sumSubtree(int u) {
// tính tống đoạn st[u]..en[u]
return sumPrefix(en[u]) - sumPrefix(st[u] - 1);
}
¶ Cập nhật đường đi - truy vấn đỉnh
Trong một bài toán cần các thao tác thay đổi giá trị các đỉnh trên đường đi và tính giá trị của đỉnh, ta cũng có thể áp dụng ứng dụng trên để giải quyết.
Gọi:
- là cha trực tiếp của đỉnh .
- là tổ tiên chung gần nhất của và .
- là một giá trị khác của đỉnh . Ban đầu, với mọi .
Giả sử cần tăng giá trị mỗi đỉnh thuộc đường đi từ đến thêm đơn vị, thực hiện các bước như sau:
- Tăng thêm đơn vị.
- Tăng thêm đơn vị
- Giảm đi đơn vị.
- Giảm đi đơn vị
Để tính giá trị của đỉnh , ta tính tổng các giá trị mà thuộc cây con gốc .
Với cách tính như vậy, thì việc cập nhật bên trên sẽ tăng giá trị của những đỉnh thuộc đường đi từ đến thêm đúng đơn vị, giá trị các đỉnh còn lại không thay đổi.
Thật vậy, sau mỗi lần tăng đường đi từ đến , xét đỉnh :
- Nếu = , giá trị đỉnh tăng thêm đơn vị do ảnh hưởng của các bước .
- Nếu thuộc đường đi từ đến nhưng không phải , giá trị đỉnh tăng thêm đơn vị do ảnh hưởng của một trong hai bước .
- Nếu là tổ tiên của (), giá trị của đỉnh không thay đổi do chịu ảnh hưởng của cả bốn bước .
- Các trường hợp còn lại, giá trị đỉnh không thay đổi vì không bị ảnh hưởng bởi bất kì bước nào.
Lưu ý rằng, giá trị đỉnh bị thay đổi khi một giá trị mà thuộc cây con gốc bị thay đổi.
Các thao tác đối với là các thao tác dạng "cập nhật đỉnh, truy vấn cây con", vì vậy có thể dễ dàng giải quyết bằng thuật toán đã nêu trước đó.
¶ Cập nhật đỉnh - truy vấn đường đi
Ứng dụng cho phép thay đổi giá trị đỉnh và tính tổng giá trị các đỉnh thuộc đường đi (ngắn nhất) giữa hai đỉnh bất kì trên cây.
Bài toán này có một cách giải khá phổ biến như sau: tạo mảng , trong đó là tổng giá trị các đỉnh trên đường đi từ đỉnh gốc đến đỉnh . Vậy khi tăng giá trị đỉnh , ta cần tăng các giá trị mà thuộc cây con gốc . Và tổng giá trị các đỉnh thuộc đường đi giữa hai đỉnh , bất kì là , trong đó là cha của tổ tiên chung gần nhất của và .
Tuy nhiên ứng dụng này muốn đề cập đến một phương pháp khác khá thú vị, mời bạn đọc cùng tìm hiểu.
Trước hết, ta cũng cần thay đổi đường đi Euler như ứng dụng trước, cụ thể:
Theo đường đi Euler, ta thêm đỉnh vào dãy khi thăm đỉnh lần đầu tiên và khi thăm đỉnh lần cuối cùng.
(Nếu đỉnh là lá, ta thêm đỉnh hai lần liên tiếp vì lần thăm đầu tiên cũng là lần thăm cuối cùng).
Ví dụ
1 2 3 2 4 2 1 5 1
=> 1 2 3 3 4 4 2 5 5 1
Cũng có thể cài đặt để đạt được mảng trực tiếp như sau:
void dfs(int u, int parent_of_u) {
tour[++m] = u;
st[u] = m;
for (int v : adj[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
tour[++m] = u;
en[u] = m;
}
là vị trí đầu tiên của đỉnh , là vị trí thứ hai của đỉnh . Mỗi đỉnh xuất hiện đúng lần.
¶ Cơ sở
Với hai đỉnh , bất kì mà là tổ tiên của , xét đoạn các giá trị từ vị trí đến vị trí của dãy , ta có:
- Các đỉnh thuộc đường đi từ đến xuất hiện đúng lần trong đoạn, cũng chính là lần đầu tiên đỉnh đó xuất hiện trong dãy .
- Các đỉnh không thuộc đường đi từ đến sẽ không xuất hiện lần nào, hoặc xuất hiện đúng hai lần trong đoạn.
Ví dụ:
Hình
Các đỉnh được tô màu khác màu đen là các đỉnh xuất hiện trong đoạn của dãy.
¶ Giải thích
Do là tổ tiên của ta có .
Trước tiên, ta không cần quan tâm đến những đỉnh không xuất hiện trong đoạn của dãy , vì những đoạn thuộc đường đi từ đến trên cây thì chắc chắn xuất hiện trong đoạn này.
Xét đỉnh xuất hiện trong đoạn của dãy :
- Nếu thuộc đường đi từ đến trên cây, nghĩa là thuộc cây con gốc và thuộc cây con gốc , vậy , xuất hiện đúng lần trên đoạn , cũng là lần thứ nhất đỉnh xuất hiện trong dãy .
- Nếu không thuộc đường đi từ đến trên cây, nghĩa là không có quan hệ tổ tiên với , ta có , vậy xuất hiện đủ lần trên đoạn.
¶ Thuật toán
Ý tưởng của thuật toán này là tạo mảng với là giá trị của đỉnh , và . Vì vậy khi tính tổng giá trị đoạn của mảng , các đỉnh xuất hiện lần sẽ tự "triệt tiêu" do , chỉ còn lại tổng các đỉnh xuất hiện một lần - các đỉnh thuộc đường đi từ đến .
Ta có thuật toán như sau:
- Khi tăng giá trị đỉnh thêm đơn vị, ta tăng giá trị tại vị trí thêm đơn vị, giảm giá trị tại vị trí đi đơn vị.
- Để tính tổng giá trị các đỉnh trên đường đi từ đến , ta tính tổng các giá trị thuộc đoạn (giả sử là tổ tiên của ).
Thuật toán chỉ áp dụng đối với đường đi từ một tổ tiên của một đỉnh về đỉnh đó. Đối với trường hợp tổng quát của và , cần chia đường đi thành 2 phần là và , hai đường đi này thỏa điều kiện trên.
¶ Tổ tiên chung gần nhất - Lowest Common Ancestor
Đường đi Euler trên cây cũng có thể được dùng để tìm tổ tiên chung gần nhất, kết hợp với cấu trúc dữ liệu RMQ.
Ứng dụng này không cần biến đổi đường đi Euler.
¶ Cơ sở
Gọi:
- là dãy đỉnh biểu diễn đường đi Euler.
- là vị trí đầu tiên của đỉnh trong dãy .
Ta có tính chất sau:
Đối với hai đỉnh , phân biệt mà , tổ tiên chung gần nhất của hai đỉnh này là giá trị thuộc đoạn của dãy sao cho khoảng cách từ đến gốc là nhỏ nhất có thể.
¶ Giải thích
Gọi là cha chung gần nhất của và .
Xét các đỉnh xuất hiện trên đoạn của dãy :
- Theo định nghĩa, đoạn này thể hiện một đoạn của đường đi Euler, bắt đầu từ đỉnh và đi đến đỉnh , vì vậy chắc chắn có chứa đỉnh .
- Vì là con của nên đoạn này không thể chứa bất cứ đỉnh nào là tổ tiên của .
Vậy đỉnh gần gốc nhất trên đoạn chính là đỉnh - tổ tiên chung gần nhất của và .
¶ Thuật toán
Gọi là khoảng cách của đỉnh đến gốc của cây. Khi tìm , ta cần tìm đỉnh thuộc đoạn mà là nhỏ nhất.
Có thể áp dụng cấu trúc dữ liệu RMQ để tìm đỉnh , độ phức tạp cho việc chuẩn bị là , độ phức tạp cho mỗi thao tác tìm là , trong đó, là độ dài của mảng lưu đường đi Euler.
Lưu ý rằng, độ dài của mảng lưu đường đi Euler có thể lớn hơn , cụ thể , vì mỗi cạnh được đi qua lần, mỗi lần qua một cạnh thì thêm một đỉnh vào đường đi, ngoại trừ cạnh đầu tiên thêm hai đỉnh vào đường đi.
Bài tập ví dụ: Company Queries II
Một công ty nọ có thành viên. Ngoại trừ tổng giám đốc, mỗi thành viên sẽ có một người sếp.
Cho thông tin về số thành viên và sếp của mỗi người, hãy trả lời truy vấn dạng với câu hỏi: ai là sếp chung thấp nhất của và .
Giới hạn:
Dưới đây là đoạn code mẫu cho bài tập trên:
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
const int K = 20;
int n, q, m = 0, h[N], st[N];
int R[2 * N][K];
//R[i][j] là giá trị u có st[u] thuộc đoạn i..i+(2^j)-1 sao cho h[u] là nhỏ nhất
vector<int> g[N];
void dfs(int u, int p) {
h[u] = h[p] + 1;
R[++m][0] = u;
st[u] = m;
for (int v : g[u]) {
if (v != p) {
dfs(v, u);
R[++m][0] = u;
}
}
}
void solve() {
cin >> n >> q;
for (int i = 2; i <= n; ++i) {
int p; cin >> p;
g[p].push_back(i);
}
dfs(1, 0);
for (int k = 0; (1 << (k + 1)) <= m; ++k) {
for (int i = 1; i + (1 << (k + 1)) - 1 <= m; ++i) {
R[i][k + 1] = (h[R[i][k]] < h[R[i + (1 << k)][k]] ? R[i][k] : R[i + (1 << k)][k]);
}
}
while (q--) {
int u, v;
cin >> u >> v;
int l = st[u], r = st[v];
if (l > r) swap(l, r);
int k = log2(r - l + 1);
cout << (h[R[l][k]] < h[R[r - (1 << k) + 1][k]] ? R[l][k] : R[r - (1 << k) + 1][k]) << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}