# Bài toán
## Subtree Query
Cho một cây có n đỉnh đánh số từ $1$ đến $n$, đỉnh $1$ là đỉnh gốc của cây. Mỗi đỉnh của cây có một giá trị gọi là giá trị của đỉnh.
Thực hiện các truy vấn thuộc một trong hai loại sau:
* $1$ $u$ $x$: Thay đổi giá trị đỉnh u thành x.
* $2$ $u$: Tính tổng giá trị các đỉnh thuộc cây con gốc u (*).
Giới hạn: $n, q \leq 10^5$.
(*): Cây con gốc $u$ 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 $u$, và tất cả các cạnh nối 2 đỉnh thuộc cây con gốc $u$. Ví dụ, cây trong hình $1$ có gốc cây là đỉnh $1$, với $u = 2$ thì cây con gốc $u$ bao gồm các phần màu xanh lá (cả cạnh và đỉnh).
## "Trâu":
Ý tưởng trâu khá đơn giản: duyệt tất cả các đỉnh con để tìm đáp án cho truy vấn loại 2.
```c++
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]; // val[u] là giá trị đỉnh u
for (int v : ke[u]) {
if (v != parent[u]) { // v là con trực tiếp của 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 1, ta chỉ thay đổi giá trị của đỉnh nên độ phức tạp cho truy vấn này là $O(1)$
* Với các truy vấn loại 2, ta cần duyệt qua tất cả các đỉnh thuộc cây con gốc $u$, trong trường hợp tệ nhất, độ phức tạp cho mỗi truy vấn như thế lên đến $O(n)$
Vậy thuật toán có độ phức tạp $O(n * q)$, quá lớn để giải được bài toán này.
Bài viết sau đây sẽ giới thiệu về 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.
# Euler tour of Tree - Đường đi Euler trên cây
Chuyển một đồ thị cây thành một đồ thị có hướng, trong đó mỗi cạnh của cây được chuyển thành $2$ cạnh có hướng, mỗi cạnh có hướng nối $2$ đỉnh tương ứng nhưng theo hai chiều ngược nhau (ví dụ: đồ thị hình $2a$ chuyển thành đồ thị hình $2b$). Thể hiện chu trình Euler trên đồ thị có hướng bằng một dãy các đỉnh, dãy đỉnh đó cũng thể hiện đường đi Euler trên cây ban đầu.
(**): [Chu trình Euler](https://vnoi.info/wiki/algo/graph-theory/euler-cycle.md) 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.
Với đồ thị hình $2a$ đườ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 của chu trình Euler trên đồ thị hình $2b$.
Có thể hiểu Euler tour là một cách biểu diễn cây chỉ bằng một dãy số. Cách này có một số tính chất đặc biệt về sự liên tiếp, từ đó cho phép áp dụng các cấu trúc dữ liệu về đoạn như BIT, Segment Tree, RMQ,... để giải quyết bài toán hiệu quả hơn.
## Một số cách biểu diễn đường đi Euler trên cây
Tùy vào mỗi bài toán, đường đi Euler còn có thể được biểu diễn theo nhiều cách khác nhau, bài viết này sẽ đề cập đến $2$ cách nữa như sau:
* Đường đi Euler rút gọn: theo đường đi Euler thông thường, ta thêm một đỉnh vào một mảng mới khi thăm đỉnh đó lần đầu tiên và khi thăm đỉnh đó lần cuối cùng. Mảng mới này cho ta cách biểu diễn khác của đường đi Euler. Trong mảng này, mỗi đỉnh xuất hiện đúng hai lần (đỉnh lá xuất hiện hai lần liên tiếp nhau, vì lần thăm đầu tiên cũng là lần thăm cuối cùng).
* Đường đi dfs: Vẫn theo đường đi Euler thông thường, nhưng ta chỉ thêm một đỉnh vào mảng mới khi thăm đỉnh đó lần đầu tiên. Mảng mới này cũng cho ta một cách biểu diễn khác về đường đi Euler, và mỗi đỉnh chỉ xuất hiện đúng một lần trong mảng này.
Không có tên gọi chính thức nào cho các biến thể vừa nêu, tuy nhiên do tính áp dụng cao, bài viết này sẽ đề cập đến các biến thể đó với tên gọi là đường đi Euler rút gọn và đường đi dfs.
Ví dụ: Theo đồ thị hình $2a$:
Đường đi Euler rút gọn: ```1 2 3 3 4 4 2 5 5 1```
Đường đi dfs: ```1 2 3 4 5```
Sau đây là ví dụ về thứ tự thăm các đối tượng của đường đi Euler theo định nghĩa, đây cũng là thứ tự thăm các đối tượng theo thuật toán dfs trên cây:
# Cài đặt
Dưới đây là cách cài đặt đường đi Euler và một số biến thể nêu trên.
Trong mỗi cách cài đặt cũng sẽ xuất hiện một số giá trị đặc biệt như $d[u]$, $st[u]$, $en[u]$, đây là những giá trị được dùng thường xuyên trong các bài toán về Euler Tour, ý nghĩa của các giá trị này sẽ được nêu rõ hơn cho từng code.
## Đường đi Euler
Tham khảo đoạn code c++ sau:
```c++
int m = 0, d[N], st[N], en[N], tour[N];
void add(int u) {
tour[++m] = u;
en[u] = m;
}
void dfs(int u, int parent_of_u) {
d[u] = d[parent_of_u] + 1;
add(u);
st[u] = m;
for (int v : ke[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
if (u != 1) add(parent_of_u);
}
int main() {
input_Graph();
dfs(1, 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 1, ta thêm cha của đỉnh vào đường đi.
Áp dụng code trên vào đồ thị hình $2a$, mảng $tour$ 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.
Giá trị $st[u]$ cho biết vị trí xuất hiện đầu tiên của $u$ trong mảng $tour$, $en[u]$ là vị trí xuất hiện cuối cùng của $u$ trong mảng $tour$, giá trị $d[u]$ cho biết khoảng cách từ đỉnh $u$ đến đỉnh gốc trên cây.
## Đường đi Euler rút gọn
```c++
int m = 0, tour[N], st[N], en[N];
void dfs(int u, int parent_of_u) {
tour[++m] = u;
st[u] = m;
for (int v : ke[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
tour[++m] = u;
en[u] = m;
}
int main() {
input_Graph();
dfs(1, 0);
return 0;
}
```
Thêm đỉnh $u$ vào $tour$ khi truy cập vào $u$ và trước khi rời khỏi $u$.
Với đồ thị hình $2a$, $tour$ chứa các giá trị: ```1 2 3 3 4 4 2 5 5 1```
Giá trị $st[u]$ lưu vị trí thứ nhất của đỉnh $u$ trên đường đi, $en[u]$ lưu vị trí thứ hai của đỉnh $u$ trên đường đi.
## Đường đi dfs
```c++
int m = 0, tour[N], st[N], en[N];
void dfs(int u, int parent_of_u) {
tour[++m] = u;
st[u] = m;
for (int v : ke[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
en[u] = m;
}
int main() {
input_Graph();
dfs(1, 0);
return 0;
}
```
Đoạn code trên chỉ thêm đỉnh $u$ vào $tour$ đúng $1$ lần (là lần đầu tiên thăm đỉnh $u$), vậy kết quả cho đồ thị hình $2a$ sẽ là ```1 2 3 4 5```
Giá trị $st[u]$ lưu vị trí của đỉnh $u$ trên đường đi, $en[u]$ cho biết vị trí cuối cùng nhất của một đỉnh thuộc cây con gốc $u$ trên đường đi.
# Tính chất và ứng dụng
Mỗi kiểu lưu trữ Euler tour có các tính chất khác nhau, các tính chất này sẽ được trình bày cụ thể trong các bài tập ví dụ sau.
## [Subtree Query](https://cses.fi/problemset/task/1137)
Tóm tắt lại bài toán:
Cho một cây $n$ đỉnh có gốc tại đỉnh 1, mỗi đỉnh có một giá trị. Cần thực hiện các truy vấn thuộc một trong hai loại:
1. Thay đổi giá trị 1 đỉnh.
2. Tính tổng giá trị tất cả các đỉnh thuộc cây con có gốc được cho trong truy vấn.
### Tính chất
Tính chất của đường đi dfs: các đỉnh thuộc cây con gốc $u$ có vị trí thuộc đoạn $st[u]..en[u]$, bất kì đỉnh nào có vị trí thuộc đoạn $st[u]..en[u]$ đều thuộc cây con gốc $u$ (xem lại phần cài đặt để rõ hơn về các giá trị $st[u]$, $en[u]$).
Nói cách khác, trên đường đi dfs, các đỉnh con của đỉnh $u$ (kể cả đỉnh $u$) sẽ nằm liên tiếp từ vị trí $st[u]..en[u]$.
### Giải thích
Nhận xét: Kể từ lúc thăm đỉnh $u$, đường đi Euler sẽ luôn đi qua tất cả đỉnh con của đỉnh $u$ trước khi trở lại đỉnh cha của đỉnh $u$. Và một khi đã trở lại đỉnh cha của $u$, đường đi sẽ không quay lại đỉnh $u$ lần nữa.
Vì vậy, các đỉnh con của đỉnh $u$ luôn nằm ở các vị trí liên tiếp nhau.
### Thuật toán
Áp dụng tính chất trên, bài toán ban đầu có thể được giải quyết theo cách sau:
* Với mỗi truy vấn loại 1, ta thay đổi giá trị tại $st[u]$
* Với mỗi truy vấn loại 2, in ra tổng các giá trị thuộc đoạn $[st[u]..en[u]]$
Để thực hiện các thao tác thay đổi và tính tổng, có thể áp dụng cấu trúc dữ liệu [Fenwick Tree (cây BIT)](https://vnoi.info/wiki/algo/data-structures/fenwick.md) hoặc [Segment Tree](https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md).
```c++
// BIT
void add(int i, int x) {
for (; i <= n; i += i & (-i)) bit[i] += x;
}
long long sum_prefix(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) {
add(st[u], -val[u] + x);
val[u] = x;
}
long long sum(int u) {
return sum_prefix(en[u]) - sum_prefix(st[u] - 1);
}
```
Độ phức tạp của mỗi truy vấn chỉ còn $O(log(n))$ (độ phức tạp của các thao tác trên cây BIT), vậy độ phức tạp của thuật toán là $O(nlog(n))$.
### Có thể bạn đã biết ?
Đường đi Euler thông thường và đường đi Euler rút gọn cũng có tính chất liên tiếp tương tự như tính chất nêu trên, tuy nhiên không phải lựa chọn tốt nhất cho bài này vì các đỉnh xuất hiện nhiều lần, các thao tác xử lý sẽ phức tạp hơn.
## LCA
Euler tour cũng có thể được ứng dụng để tìm cha chung gần nhất.
### Tính chất
Xem lại đoạn code sau:
```c++
int m = 0, d[N], en[N], tour[N];
void add(int u) {
tour[++m] = u;
en[u] = m;
}
void dfs(int u, int parent_of_u) {
d[u] = d[parent_of_u] + 1;
add(u);
for (int v : ke[u]) {
if (v != parent_of_u) {
dfs(v, u);
}
}
if (u != 1) add(parent_of_u);
}
int main() {
input_Graph();
dfs(1, 0);
return 0;
}
```
$en[u]$ là vị trí cuối cùng của đỉnh $u$ trên mảng $tour$.
$d[u]$ là khoảng cách từ đỉnh gốc đến đỉnh $u$.
Đối với hai đỉnh $u$, $v$ phân biệt mà $en[u] \leq en[v]$, cha chung gần nhất của hai đỉnh này là giá trị $p$ thuộc đoạn $en[u]..en[v]$ của mảng $tour$ sao cho $d[p]$ là nhỏ nhất có thể.
Ví dụ: Cần tìm cha chung gần nhất của đỉnh $6$ và đỉnh $7$ trong đồ thị hình trên:
Ta có $en[6] = 9$ và $en[7] = 11$, đoạn các giá trị từ vị trí $en[6]$ đến vị trí $en[7]$ trong mảng $tour$ là $6$ $5$ $7$. Trong đoạn này, đỉnh gần gốc nhất là đỉnh 5, cũng chính là cha chung gần nhất của $6$ và $7$.
### Giải thích
Như nhận xét của phần trước, kể từ khi thăm đỉnh $u$, đường đi Euler sẽ luôn thăm qua tất cả đỉnh thuộc cây con gốc $u$ trước khi trở về cha $u$.
Gọi $p$ là cha chung gần nhất của $u$ và $v$.
Xét các giá trị trên đoạn $en[u]..en[v]$ của mảng $tour$:
+ 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 $u$ và đi đến đỉnh $v$. Vì vậy giá trị $p$ chắc chắn xuất hiện trên đoạn này.
+ Vì $v$ là con của $p$ nên đoạn này không thể chứa bất cứ đỉnh nào là tổ tiên của $p$.
Vậy đỉnh gần gốc nhất xuất hiện trên đoạn $en[u]..en[v]$ chính là đỉnh $p$ - cha chung gần nhất của $u$ và $v$.
### Thuật toán
Dựa theo tính chất bên trên, có thể dùng cấu trúc dữ liệu [Segment Tree](https://vnoi.info/wiki/algo/data-structures/segment-tree-extend.md) hoặc [RMQ](https://vnoi.info/wiki/translate/topcoder/Range-Minimum-Query-and-Lowest-Common-Ancestor.md) để xử lý.
Độ phức tạp của việc chuẩn bị là $O(nlog(n))$, độ phức tạp cho mỗi lần tìm cha chung gần nhất là $O(log(n))$ (đối với Segment Tree) hoặc $O(1)$ (đối với RMQ).
# Luyện tập
### [Distinct Colors - CSES](https://cses.fi/problemset/task/1139)
### [Path Queries - CSES](https://cses.fi/problemset/task/1138)
### [Hemose in ICPC ? - Codeforces](https://codeforces.com/problemset/problem/1592/D)
Sign in with Wallet
Connect another wallet