---
# System prepended metadata

title: Euler tour - Review2

---

# Euler tour - Review2
Người review: Quang Anh | coffee
Note cho Hậu: hackmd này chỉ là copy paste lại comment của mình trong bài gốc của bạn thôi, nên lúc bạn edit thì cứ vào thẳng đấy cho nhanh. 

# Tổng quan
Đống phía dưới đa phần là mình bắt lỗi lặt vặt, thêm bớt từ, chuyển vị trí các câu,... là chính. Nói cách khác, những cái bạn viết mình thấy rất oke 🍀 

# Cụ thể

## Subtree Query 
### "Trâu"

> *Phần code* 
 
Mình thấy tên các biến khác đều là tiếng anh (val[], parent[],...) nên có khi thay luôn "ke" thành "adj" hoặc gì đó tương tự cho nó đồng bộ 

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

Câu này mình nghĩ nên cho lên đầu (đồng nghĩa phải viết lại một chút) như là câu "mở bài", để cho người đọc biết tại sao mình lại quan tâm tới bài toán Subtree Query ý :3 

## Euler tour of Tree - Đường đi Euler trên cây

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

Mình nghĩ nên thay "Cách" -> "Dãy số"

### Một số cách biểu diễn đường đi Euler trên cây

> 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:

Thêm animation mình thấy là hợp lý, nhưng theo mình thì cái animation này nên để lên phần trên, chỗ "1 2 3 2 4 2 1 5 1" để người đọc dễ hình dung phần đó hơn. Ngoài ra nếu có thể thì nút nào đang là màu xanh thì bạn có thể highlight phần tử tương ứng trong dãy số, hơi mất thời gian nma nó đẹp uwu

## Cài đặt 

### Đường đi Euler

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

Phần giải thích tên biến có thể hoặc 1. Để dưới dạng comment trong code hoặc 2. Cho vào đoạn văn đầu tiên sau code thì mình nghĩ xuôi hơn (tại thường mình nhìn thấy code là mình ngắm code một lúc mới xuống xem giải thích ở dưới). > <

Các code sau mình nghĩ cũng nên làm tương tự.

## Tính chất và ứng dụng

### Subtree Query

#### 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]$... 

Mình nghĩ để rõ hơn thì chỗ bôi đen 1 nên ghi là "các đỉnh v thuộc cây con gốc u có st[v]", hoặc đơn giản hơn: "$st[u] \leq st[v] \leq en[v] \leq en[u]$".

Chỗ bôi đen 2: "vị trí" -> "$st$"

#### Giải thích 
> Vì vậy, các đỉnh con của đỉnh $u$ luôn nằm ở các vị trí liên tiếp nhau.

Đúng, nhưng chưa đủ để giải thích sao nó phải trong khoảng $[st[u], en[u]]$. Chỗ này bạn thêm 1 dòng giải thích nữa mình nghĩ là ổn. 

### LCA
Mình nghĩ lần đầu nhắc đến thì viết hẳn ra là "Least common ancestor", từ các lần sau thì gọi tắt.

Nếu mình nhớ không nhầm thì VNOI cũng có sắn một bài về LCA, bạn có thể paste url bài đó vào cho đầy đủ.

> Euler tour cũng có thể được ứng dụng để tìm **cha** chung gần nhất.

"cha" -> "tổ tiên" (/s in case có độc giả nào kêu thuật ngữ không gender-neutral thì vnoi đỡ nhận gạch thôi chứ cái này thực ra ko sao hihi ><)

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

Mình nghĩ nên thêm một từ đánh dấu để biết là đây là một tính chất mới có giải thích đằng sau chứ không phải là một nhận xét rút ra từ các phần trước, do là mình đọc phần này mình tưởng không có giải thích, đến lúc kéo xuống mới thấy có rồi. 

Chẳng hạn bạn có thể viết "**Định lý:**" or something, sửa thế nào cũng oke hết miễn là cả bài đều dùng chung một format như thế.

**Hết rùi uwu**